# Constructing an odd-even mergesort sorting network

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

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 <stdlib.h>
#include <stdio.h>

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

for (int p=1; p<n; p+=p)
for (int k=p; k>0; k/=2)
for (int j=k%p; j+k<n; j+=(k+k))
for (int i=0; i<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 << 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 <stdlib.h>
#include <stdio.h>

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

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);
}
}
}
}
}
}
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.
• One code snippet has 4 loops, and one has 5 loops. Which one are you looking for a review on specifically? Also, I hope this is mostly just an educational exercise, as these algorithms are O(n⁴) and O(n⁵) respectively and should never be used in real world application. – syb0rg Dec 23 '15 at 16:16
• The second snippet is for review. The first one is from a book and not correct. The space complexity of the algorithm is O(n * log n * log n) not O(n^5) and the time complexity is O(log n * log n). 5 for-loops are needed to linearize the recursive variant. See Wikipedia for more details and a recursive implementation. As far as I know this is the fastest sorting network. Keep in mind that hardware performs every step in parallel unless there are data dependencies. Each column in the picture shows m parallel operations per point in time. – Paebbels Dec 23 '15 at 16:55
• The O(n⁵) was referring to the time complexity, which is what is typically referred to when talking about Big O and not specifying the complexity it relates to. I'm still having a hard time believing this algorithm is O(log n * log n), but arguing such small aspects about that is somewhat irrelevant anyways. – syb0rg Dec 24 '15 at 4:07

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 <stdlib.h>
#include <stdio.h>

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

void sort(int length)
{
int groups = log2ceil(length);
for (int group = 0; group < groups; group++)
{
int blocks = 1 << (groups - group - 1);
for (int block = 0; block < blocks; block++)
{
for (int stage = 0; stage <= group; stage++)
{
int distance = 1 << (group - stage);
int startPoint = (stage == 0) ? 0 : distance;
for (int j = startPoint; j + distance < (2 << group); j += 2 * distance)
{
for (int i = 0; i < 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);
}