Constructing an odd-even mergesort sorting network I was searching for a non-recursive odd-even mergesort implementation and found this one:


Sedgewick R.


The resulting sorting network is not an odd-even-merge sort network. When one draws a diagram of the pairs, it can be seen that too many pairs are generated and others are missed.

So here is an image of a correct network with 32 inputs. A vertical line between 2 horizontal lines means compare value a[x] with a[y], if greater then swap the values in the array.

 (clickable)

The code from the book translated into C:

#include &lt;stdlib.h&gt;
#include &lt;stdio.h&gt;

void sort(int l, int r)
{ int n = r-l+1;

  for (int p=1; p&lt;n; p+=p)
    for (int k=p; k&gt;0; k/=2)
      for (int j=k%p; j+k&lt;n; j+=(k+k))
        for (int i=0; i&lt;n-j-k; i++)
          if ((j+i)/(p+p) == (j+i+k)/(p+p))
              printf("%2i cmp %2i\n", l+j+i, l+j+i+k);
}
int main(char* argv, int args)
{ const int COUNT = 8;
  sort(0, COUNT-1);
}


See my StackOverflow question for more details and a diagram for the falsly generated network.

So I took the sorting network images for length = 1 &lt;&lt; i and tried to write an algorithm that generates 2 indices x and y. These are needed to calculate the resource consumption of the sorting network in hardware.

I checked my function with length = 2, 4, 8, 16.

Here is my C code:

#include &lt;stdlib.h&gt;
#include &lt;stdio.h&gt;

int log2ceil(int a)
{ int i;
  int cmp = 1;
  for (i = 0; cmp &lt; a; i++)
  { cmp &lt;&lt;= 1; }
  return i;
}

void sort(int length)
{ int G = log2ceil(length);                      // number of groups
  for (int g = 0; g &lt; G; g++)                    // iterate groups
  { int B = 1 &lt;&lt; (G - g - 1);                    // number of blocks
    for (int b = 0; b &lt; B; b++)                  // iterate blocks in a group
    { for (int s = 0; s &lt;= g; s++)               // iterate stages in a block
      { int d = 1 &lt;&lt; (g - s);                    // compare distance
        int J = (s == 0) ? 0 : d;                // starting point
        for (int j = J; j+d &lt; (2&lt;&lt;g); j += 2*d)  // iterate startpoints
        { for (int i = 0; i &lt; 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);
          }
        }
      }
    }
  }
}
int main(char* argv, int args)
{ const int COUNT = 8;
  sort(COUNT);
}



Is it correct?
Can it be improved? E.g. just 4 loops.
It need not be very fast, because it's a hardware generation and check routine.
In general your code is quite hard to comprehend due to the bracing style and the single letter variable names. A bit more spaces and more meaningful names would do quite a bit for readability (I've kept your 2-indent spacing) and also remove the need for most of the comments:

#include &lt;stdlib.h&gt;
#include &lt;stdio.h&gt;

int log2ceil(int value)
{
  int i;
  int cmp = 1;
  for (i = 0; cmp &lt; value; i++)
  {
    cmp &lt;&lt;= 1;
  }
  return i;
}

void sort(int length)
{
  int groups = log2ceil(length);
  for (int group = 0; group &lt; groups; group++)
  {
    int blocks = 1 &lt;&lt; (groups - group - 1);
    for (int block = 0; block &lt; blocks; block++)
    {
      for (int stage = 0; stage &lt;= group; stage++)
      {
        int distance = 1 &lt;&lt; (group - stage);
        int startPoint = (stage == 0) ? 0 : distance;
        for (int j = startPoint; j + distance &lt; (2 &lt;&lt; group); j += 2 * distance)
        {
          for (int i = 0; i &lt; distance; i++)            // shift startpoints
          {
            int x = (block * (length / blocks)) + j + i;
            int y = x + distance;
            printf("%2i cmp %2i\n", x, y);
          }
        }
      }
    }
  }
}

int main(char* argv, int args)
{
  const int COUNT = 8;
  sort(COUNT);
}