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