added latency tool
[tridge/junkcode.git] / 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 }