batchers.c

   1 #include <stdio.h>
   2
   3 static void batchers_sort(int baseP,int N,void (*makesmaller)())
   4 {
   5   int   p, initq, q, r, d, x;
   6
   7   for (p=1; (1<<(p+1))<=N+1; p++);
   8   p = 1<<p;
   9
  10   for (initq=p; p>0; p/=2)
  11     {
  12       q = initq;
  13       r = 0;
  14       d = p;
  15       do
  16         {
  17           for (x=0; x<N-d; x++)
  18             if ( (x & p) == r)
  19               makesmaller(baseP+x,baseP+x+d);
  20           d = q - p;
  21           q /= 2;
  22           r = p;
  23         } while (q != p/2);
  24     }
  25 }
  26
  27 void makesmaller(int n1,int n2)
  28 {
  29   printf("%d %d\n",n1,n2);
  30 }
  31
  32 main(int argc,char *argv[])
  33 {
  34   batchers_sort(0,atoi(argv[1]),makesmaller);
  35 }