Return to Question

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

odd-even-merge sort for 32 inputs (clickable)

For context the code from the book translated into C:

#include <stdlib.h>
#include <stdio.h>
void sort(int l, int r)
/* transscribed from Program 11.4 batchersortNR() in
 * Robert Sedgewick's 2002
 * "Algorithms in Java", Parts 1-4 (3rd Edition) */
{ 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", l+j+i, l+j+i+k);
}
int main(char* argv, int args)
{ const int COUNT = 8;
 sort(0, COUNT-1);
}

odd-even-merge sort for 32 inputs (clickable)

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

• Is it correct?
• Can it be improved? E.g. just 4 loops.
• It must not be very fast, because it's a hardware generation and check routine.

odd-even-merge sort for 32 inputs (clickable)

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

• 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.

odd-even-merge sort for 32 inputs http://flylib.com/books/3/55/1/html/2/images/11fig07.gif (clickable)

odd-even-merge sort for 32 inputs (clickable)