1 /* Sort.c -- Sort functions
2 2014-04-05 : Igor Pavlov : Public domain */
8 #define HeapSortDown(p, k, size, temp) \
10 size_t s = (k << 1); \
11 if (s > size) break; \
12 if (s < size && p[s + 1] > p[s]) s++; \
13 if (temp >= p[s]) break; \
17 void HeapSort(UInt32 *p, size_t size)
28 HeapSortDown(p, k, size, temp)
36 UInt32 temp = p[size];
38 HeapSortDown(p, k, size, temp)
44 UInt32 temp = p[size];
45 size_t k = (p[3] > p[2]) ? 3 : 2;
48 HeapSortDown(p, k, size, temp)
51 UInt32 temp = p[size];
53 if (size > 2 && p[2] < temp)
63 void HeapSort64(UInt64 *p, size_t size)
74 HeapSortDown(p, k, size, temp)
82 UInt64 temp = p[size];
84 HeapSortDown(p, k, size, temp)
90 UInt64 temp = p[size];
91 size_t k = (p[3] > p[2]) ? 3 : 2;
94 HeapSortDown(p, k, size, temp)
97 UInt64 temp = p[size];
99 if (size > 2 && p[2] < temp)
110 #define HeapSortRefDown(p, vals, n, size, temp) \
111 { size_t k = n; UInt32 val = vals[temp]; for (;;) { \
112 size_t s = (k << 1); \
113 if (s > size) break; \
114 if (s < size && vals[p[s + 1]] > vals[p[s]]) s++; \
115 if (val >= vals[p[s]]) break; \
116 p[k] = p[s]; k = s; \
119 void HeapSortRef(UInt32 *p, UInt32 *vals, size_t size)
129 HeapSortRefDown(p, vals, i, size, temp);
135 UInt32 temp = p[size];
137 HeapSortRefDown(p, vals, 1, size, temp);