1 module rt.compiler.gdc.rt.qsortg;
2 struct Array
3 {
4 size_t length;
5 void* ptr;
6 }
7
8 extern (C) Array _adSort(Array a, TypeInfo ti)
9 {
10 static const uint Qsort_Threshold = 7;
11
12 struct StackEntry {
13 byte *l;
14 byte *r;
15 }
16
17 size_t elem_size = ti.tsize();
18 size_t qsort_limit = elem_size * Qsort_Threshold;
19
20 static assert(ubyte.sizeof == 1);
21 static assert(ubyte.max == 255);
22
23 StackEntry[size_t.sizeof * 8] stack; // log2( size_t.max )
24 StackEntry * sp = stack.ptr;
25 byte* lbound = cast(byte *) a.ptr;
26 byte* rbound = cast(byte *) a.ptr + a.length * elem_size;
27 byte* li = void;
28 byte* ri = void;
29
30 while (1)
31 {
32 if (rbound - lbound > qsort_limit)
33 {
34 ti.swap(lbound,
35 lbound + (
36 ((rbound - lbound) >>> 1) -
37 (((rbound - lbound) >>> 1) % elem_size)
38 ));
39
40 li = lbound + elem_size;
41 ri = rbound - elem_size;
42
43 if (ti.compare(li, ri) > 0)
44 ti.swap(li, ri);
45 if (ti.compare(lbound, ri) > 0)
46 ti.swap(lbound, ri);
47 if (ti.compare(li, lbound) > 0)
48 ti.swap(li, lbound);
49
50 while (1)
51 {
52 do
53 li += elem_size;
54 while (ti.compare(li, lbound) < 0);
55 do
56 ri -= elem_size;
57 while (ti.compare(ri, lbound) > 0);
58 if (li > ri)
59 break;
60 ti.swap(li, ri);
61 }
62 ti.swap(lbound, ri);
63 if (ri - lbound > rbound - li)
64 {
65 sp.l = lbound;
66 sp.r = ri;
67 lbound = li;
68 }
69 else
70 {
71 sp.l = li;
72 sp.r = rbound;
73 rbound = ri;
74 }
75 ++sp;
76 } else {
77 // Use insertion sort
78 for (ri = lbound, li = lbound + elem_size;
79 li < rbound;
80 ri = li, li += elem_size)
81 {
82 for ( ; ti.compare(ri, ri + elem_size) > 0;
83 ri -= elem_size)
84 {
85 ti.swap(ri, ri + elem_size);
86 if (ri == lbound)
87 break;
88 }
89 }
90 if (sp != stack.ptr)
91 {
92 --sp;
93 lbound = sp.l;
94 rbound = sp.r;
95 }
96 else
97 return a;
98 }
99 }
100 }
101
102 unittest
103 {
104 static void check(int[] a) {
105 for (uint i = 1; i < a.length; i++)
106 assert(a[i-1] <= a[i]);
107 }
108
109 static int[] t1 = [ 4, 3, 19, 7, 6, 20, 11, 1, 2, 5 ];
110 int[] a;
111
112 a = t1;
113 a.sort;
114 check(a);
115 }