How to fix this non-recursive odd-even-merge sort algorithm?

The following code works for arrays of any size and isn't recursive. It is a straight port from the implementation of the corresponding function in Perl's Algorithm::Networksort module. The implementation happens to correspond to the algorithm as described by Knuth in The Art of Computer Programming, vol 3 (algorithm 5.2.2M). It doesn't help to actually fix your algorithm, but it at least gives you a working non-recursive implementation of Batcher's odd-even mergesort with only three nested loops :)

#include <math.h>
#include <stdio.h>

void oddeven_merge_sort(int length)
{
    int t = ceil(log2(length));
    int p = pow(2, t - 1);

    while (p > 0) {
        int q = pow(2, t - 1);
        int r = 0;
        int d = p;

        while (d > 0) {
            for (int i = 0 ; i < length - d ; ++i) {
                if ((i & p) == r) {
                    printf("%2i cmp %2i\n", i, i + d);
                }
            }

            d = q - p;
            q /= 2;
            r = p;
        }
        p /= 2;
    }
}

If you can get your hands on a copy of The Art of Computer Programming, vol 3, you will have a nice explanation of how and why the algorithm works, as well as a few additional details.

I think I found a solution. I checked it for length = 2, 4, 8, 16.

Here is my code:

void sort(int length)
{ int G = log2ceil(length);                      // number of groups
  for (int g = 0; g < G; g++)                    // iterate groups
  { int B = 1 << (G - g - 1);                    // number of blocks
    for (int b = 0; b < B; b++)                  // iterate blocks in a group
    { for (int s = 0; s <= g; s++)               // iterate stages in a block
      { int d = 1 << (g - s);                    // compare distance
        int J = (s == 0) ? 0 : d;                // starting point
        for (int j = J; j+d < (2<<g); j += 2*d)  // iterate startpoints
        { for (int i = 0; i < d; i++)            // shift startpoints
          { int x = (b * (length / B)) + j + i;  // index 1
            int y = x + d;                       // index 2
            printf("%2i cmp %2i\n", x, y);
          }
        }
      }
   }
}

This solution introduces a fifth for-loop to handle subblocks in a group. The j loop has a changed start and abort value to handle odd counts of post merge steps without generating doubled compare steps.