8
\$\begingroup\$

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.

odd-even-merge sort for 32 inputs (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.
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – syb0rg Dec 23 '15 at 16:16
  • \$\begingroup\$ 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. \$\endgroup\$ – Paebbels Dec 23 '15 at 16:55
  • \$\begingroup\$ 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. \$\endgroup\$ – syb0rg Dec 24 '15 at 4:07
3
\$\begingroup\$

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);
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.