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

Question

I was searching for non-recursive odd-even-merge sort algorithm and found 2 sources:

• a book from Sedgewick R.
• this SO question

Both algorithms are identical but false. The resulting sorting network is not an odd-even-merge sort network.

Here is an image of the resulting 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.

_{(source: flylib.com)}
(clickable)

I copied the code from Java to C and replaced the exch function by a printf to print the exchange candidates.

When one draws a diagram of the pairs, it can be seen that too many pairs are generated.

Has anyone an idea how to fix this algorithm?

Why do I need non-recursive version?
I want to transform this sorting network into hardware. It's easy to insert pipeline stages into a non-recursive algorithms.

I also investigated the recursive version, but it's too complex to transform the algorithm into pipelined hardware.

My C code:

#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);
}

The result:

0 -o--------o-------------------------o---------------o-------------------------
   |        |                         |               |
1 -o--------|-o------o----------------|-o-------------o-o-----------------------
            | |      |                | |               |
2 -o-o------o-|------o-o--------------|-|-o----o--------o-o---------------------
   | |        |        |              | | |    |          |
3 -o-o--------o--------o--------------|-|-|-o--|-o--------o-o-------o-----------
                                      | | | |  | |          |       |
4 -o-o-o----o---o----o-----o----------o-|-|-|--o-|-o--------o-o-----o-o---------
   | | |    |   |    |     |            | | |    | |          |       |
5 -o-o-o----|-o-|-o--o-o---o-o---o------o-|-|----o-|-o--------o-o-----o-o---o---
            | | | |    |     |   |        | |      | |          |       |   |
6 -o-o-o-o--o-|-o-|----o-o---o-o-o-o------o-|------o-|----------o-o-----o-o-o-o-
   | | | |    |   |      |     |   |        |        |            |       |   |
7 -o-o-o-o----o---o------o-----o---o--------o--------o------------o-------o---o-

When I know the correct exchange pairs and the algorithm is equal to the image, I'll translate it into VHDL for tests on my hardware platform.

Other open source hardware sorting network implementations:

• PoC.sort.sortnet.oddevensort
• PoC.sort.sortnet.bitonicsort

---

Appendix:
Odd-even mergesort (a.k.a Batcher's sort) is like bitonic sort (not to confuse with Batcher's bitonic sort). But in hardware this algorithm has a better size complexity than bitonic sort, while latency is the same.

These algorithm can be implemented with good resource usage compared to fast software algorithms like quicksort.

Wikipedia: odd-even mergesort

Note:
Because sorting networks are static and independent of the input values, no compare and swap is needed to generate the network. That's one reason why it can be transformed into hardware. My code generates the indices for the compare operations. In hardware, these vertical connections will be replaced by compare and swap circuits. So unsorted data will travel throught the network and on the output side it will be sorted.

Answer 1

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.