1 #include "mssort.h"
2 #include "alloc.h"
3 #include "byte.h"
4 #include <stdlib.h> /* qsort: fallback */
5 
mssort(char * base,uint32 n,uint32 elesize,int (* cmp)(const void *,const void *))6 void mssort (char *base, uint32 n, uint32 elesize,
7                   int (*cmp) (const void *, const void *))
8 {
9   char *v;
10   char buf[64];
11   const uint32 dists[]={
12     1, 5, 19, 41, 109, 209, 505, 929,
13     2161, 3905, 8929, 16001, 36289, 64769, 146305, 260609,
14     587521, 1045505, 2354689, 4188161, 9427969, 16764929, 37730305, 67084289,
15     0
16   };
17   int distp;
18   if (n==1) return;
19   if (elesize<=sizeof(buf))
20     v=buf;
21   else {
22     v=alloc(elesize);
23     if (!v)
24       return qsort(base,n,elesize,cmp);
25   }
26   for (distp=1;dists[distp] && dists[distp]<n;distp++)
27     /* nothing */;
28   distp--;
29   while(1) {
30     uint32 h=dists[distp];
31     uint32 i,j;
32     for (i=h;i<n;i++) {
33       j=i;
34       byte_copy(v,elesize,base+i*elesize);
35       while (j>=h && cmp(base+(j-h)*elesize,v)>0) {
36 	byte_copy(base+j*elesize,elesize,base+(j-h)*elesize);
37 	j-=h;
38       }
39       byte_copy(base+j*elesize,elesize,v);
40     }
41     if (!distp)
42       break;
43     distp--;
44   }
45   if (v!=buf)
46     alloc_free(v);
47 }
48 
49