Dist m4ri 0.16.1
Computing distance of a classical or quantum CSS code
Loading...
Searching...
No Matches
sort.h
Go to the documentation of this file.
1/* Copyright (c) 2010-2024 Christopher Swenson. */
2/* Copyright (c) 2012 Vojtech Fried. */
3/* Copyright (c) 2012 Google Inc. All Rights Reserved. */
4
5#include <stdlib.h>
6#include <stdio.h>
7#include <string.h>
8#include <stdint.h>
9
10#ifndef SORT_NAME
11#error "Must declare SORT_NAME"
12#endif
13
14#ifndef SORT_TYPE
15#error "Must declare SORT_TYPE"
16#endif
17
18#ifndef SORT_CMP
19#define SORT_CMP(x, y) ((x) < (y) ? -1 : ((y) < (x) ? 1 : 0))
20#endif
21
22#ifndef SORT_DEF
23#define SORT_DEF
24#else
25#ifdef __GNUC__
26#define SORT_GCC_PUSH
27#pragma GCC diagnostic push
28#pragma GCC diagnostic ignored "-Wunused-function"
29#endif
30#endif
31
32#ifdef __cplusplus
33#ifndef SORT_SAFE_CPY
34#define SORT_SAFE_CPY 0
35#endif
36#else
37#undef SORT_SAFE_CPY
38#define SORT_SAFE_CPY 0
39#endif
40
41#ifndef TIM_SORT_STACK_SIZE
42#define TIM_SORT_STACK_SIZE 128
43#endif
44
45#ifndef SORT_SWAP
46#define SORT_SWAP(x,y) {SORT_TYPE _sort_swap_temp = (x); (x) = (y); (y) = _sort_swap_temp;}
47#endif
48
49/* Common, type-agnostic functions and constants that we don't want to declare twice. */
50#ifndef SORT_COMMON_H
51#define SORT_COMMON_H
52
53#ifndef MAX
54#define MAX(x,y) (((x) > (y) ? (x) : (y)))
55#endif
56
57#ifndef MIN
58#define MIN(x,y) (((x) < (y) ? (x) : (y)))
59#endif
60
61static int compute_minrun(const uint64_t);
62
63/* From http://oeis.org/classic/A102549 */
64static const uint64_t shell_gaps[48] = {1, 4, 10, 23, 57, 132, 301, 701, 1750, 4376, 10941, 27353, 68383, 170958, 427396, 1068491, 2671228, 6678071, 16695178, 41737946, 104344866, 260862166, 652155416, 1630388541, 4075971353LL, 10189928383LL, 25474820958LL, 63687052396LL, 159217630991LL, 398044077478LL, 995110193696LL, 2487775484241LL, 6219438710603LL, 15548596776508LL, 38871491941271LL, 97178729853178LL, 242946824632946LL, 607367061582366LL, 1518417653955916LL, 3796044134889791LL, 9490110337224478LL, 23725275843061196LL, 59313189607652991LL, 148282974019132478LL, 370707435047831196LL, 926768587619577991LL, 2316921469048944978LL, 5792303672622362446LL};
65
66#ifndef CLZ
67/* clang-only */
68#ifndef __has_builtin
69#define __has_builtin(x) 0
70#endif
71#if __has_builtin(__builtin_clzll) || (defined(__GNUC__) && ((__GNUC__ == 3 && __GNUC_MINOR__ >= 4) || (__GNUC__ > 3)))
72#define CLZ __builtin_clzll
73#else
74
75static int clzll(uint64_t);
76
77/* adapted from Hacker's Delight */
78static int clzll(uint64_t x) {
79 int n;
80
81 if (x == 0) {
82 return 64;
83 }
84
85 n = 0;
86
87 if (x <= 0x00000000FFFFFFFFL) {
88 n = n + 32;
89 x = x << 32;
90 }
91
92 if (x <= 0x0000FFFFFFFFFFFFL) {
93 n = n + 16;
94 x = x << 16;
95 }
96
97 if (x <= 0x00FFFFFFFFFFFFFFL) {
98 n = n + 8;
99 x = x << 8;
100 }
101
102 if (x <= 0x0FFFFFFFFFFFFFFFL) {
103 n = n + 4;
104 x = x << 4;
105 }
106
107 if (x <= 0x3FFFFFFFFFFFFFFFL) {
108 n = n + 2;
109 x = x << 2;
110 }
111
112 if (x <= 0x7FFFFFFFFFFFFFFFL) {
113 n = n + 1;
114 }
115
116 return n;
117}
118
119#define CLZ clzll
120#endif
121#endif
122
123static __inline int compute_minrun(const uint64_t size) {
124 const int top_bit = 64 - CLZ(size);
125 const int shift = MAX(top_bit, 6) - 6;
126 const int minrun = (int)(size >> shift);
127 const uint64_t mask = (1ULL << shift) - 1;
128
129 if (mask & size) {
130 return minrun + 1;
131 }
132
133 return minrun;
134}
135
136static __inline size_t rbnd(size_t len) {
137 int k;
138
139 if (len < 16) {
140 return 2;
141 }
142
143 k = 62 - CLZ(len);
144 return 1ULL << ((2 * k) / 3);
145}
146
147#endif /* SORT_COMMON_H */
148
149#define SORT_CONCAT(x, y) x ## _ ## y
150#define SORT_MAKE_STR1(x, y) SORT_CONCAT(x,y)
151#define SORT_MAKE_STR(x) SORT_MAKE_STR1(SORT_NAME,x)
152
153#ifndef SMALL_SORT_BND
154#define SMALL_SORT_BND 16
155#endif
156#ifndef SMALL_SORT
157#define SMALL_SORT BITONIC_SORT
158/*#define SMALL_SORT BINARY_INSERTION_SORT*/
159#endif
160#ifndef SMALL_STABLE_SORT
161#define SMALL_STABLE_SORT BINARY_INSERTION_SORT
162#endif
163
164#define SORT_TYPE_CPY SORT_MAKE_STR(sort_type_cpy)
165#define SORT_TYPE_MOVE SORT_MAKE_STR(sort_type_move)
166#define SORT_NEW_BUFFER SORT_MAKE_STR(sort_new_buffer)
167#define SORT_DELETE_BUFFER SORT_MAKE_STR(sort_delete_buffer)
168#define BITONIC_SORT SORT_MAKE_STR(bitonic_sort)
169#define BINARY_INSERTION_FIND SORT_MAKE_STR(binary_insertion_find)
170#define BINARY_INSERTION_SORT_START SORT_MAKE_STR(binary_insertion_sort_start)
171#define BINARY_INSERTION_SORT SORT_MAKE_STR(binary_insertion_sort)
172#define REVERSE_ELEMENTS SORT_MAKE_STR(reverse_elements)
173#define COUNT_RUN SORT_MAKE_STR(count_run)
174#define CHECK_INVARIANT SORT_MAKE_STR(check_invariant)
175#define TIM_SORT SORT_MAKE_STR(tim_sort)
176#define TIM_SORT_RESIZE SORT_MAKE_STR(tim_sort_resize)
177#define TIM_SORT_MERGE SORT_MAKE_STR(tim_sort_merge)
178#define TIM_SORT_COLLAPSE SORT_MAKE_STR(tim_sort_collapse)
179#define HEAP_SORT SORT_MAKE_STR(heap_sort)
180#define MEDIAN SORT_MAKE_STR(median)
181#define QUICK_SORT SORT_MAKE_STR(quick_sort)
182#define MERGE_SORT SORT_MAKE_STR(merge_sort)
183#define MERGE_SORT_RECURSIVE SORT_MAKE_STR(merge_sort_recursive)
184#define MERGE_SORT_IN_PLACE SORT_MAKE_STR(merge_sort_in_place)
185#define MERGE_SORT_IN_PLACE_RMERGE SORT_MAKE_STR(merge_sort_in_place_rmerge)
186#define MERGE_SORT_IN_PLACE_BACKMERGE SORT_MAKE_STR(merge_sort_in_place_backmerge)
187#define MERGE_SORT_IN_PLACE_FRONTMERGE SORT_MAKE_STR(merge_sort_in_place_frontmerge)
188#define MERGE_SORT_IN_PLACE_ASWAP SORT_MAKE_STR(merge_sort_in_place_aswap)
189#define SHELL_SORT SORT_MAKE_STR(shell_sort)
190#define QUICK_SORT_PARTITION SORT_MAKE_STR(quick_sort_partition)
191#define QUICK_SORT_RECURSIVE SORT_MAKE_STR(quick_sort_recursive)
192#define HEAP_SIFT_DOWN SORT_MAKE_STR(heap_sift_down)
193#define HEAPIFY SORT_MAKE_STR(heapify)
194#define TIM_SORT_RUN_T SORT_MAKE_STR(tim_sort_run_t)
195#define TEMP_STORAGE_T SORT_MAKE_STR(temp_storage_t)
196#define PUSH_NEXT SORT_MAKE_STR(push_next)
197
198#ifndef MAX
199#define MAX(x,y) (((x) > (y) ? (x) : (y)))
200#endif
201#ifndef MIN
202#define MIN(x,y) (((x) < (y) ? (x) : (y)))
203#endif
204#ifndef SORT_CSWAP
205#define SORT_CSWAP(x, y) { if(SORT_CMP((x),(y)) > 0) {SORT_SWAP((x),(y));}}
206#endif
207
208typedef struct {
209 size_t start;
210 size_t length;
211} TIM_SORT_RUN_T;
212
213
214SORT_DEF void SHELL_SORT(SORT_TYPE *dst, const size_t size);
215SORT_DEF void BINARY_INSERTION_SORT(SORT_TYPE *dst, const size_t size);
216SORT_DEF void HEAP_SORT(SORT_TYPE *dst, const size_t size);
217SORT_DEF void QUICK_SORT(SORT_TYPE *dst, const size_t size);
218SORT_DEF void MERGE_SORT(SORT_TYPE *dst, const size_t size);
219SORT_DEF void MERGE_SORT_IN_PLACE(SORT_TYPE *dst, const size_t size);
220SORT_DEF void TIM_SORT(SORT_TYPE *dst, const size_t size);
221SORT_DEF void BITONIC_SORT(SORT_TYPE *dst, const size_t size);
222
223/* The full implementation of a bitonic sort is not here. Since we only want to use
224 sorting networks for small length lists we create optimal sorting networks for
225 lists of length <= 16 and call out to BINARY_INSERTION_SORT for anything larger
226 than 16.
227 Optimal sorting networks for small length lists.
228 Taken from https://pages.ripco.net/~jgamble/nw.html */
229#define BITONIC_SORT_2 SORT_MAKE_STR(bitonic_sort_2)
230static __inline void BITONIC_SORT_2(SORT_TYPE *dst) {
231 SORT_CSWAP(dst[0], dst[1]);
232}
233
234
235#define BITONIC_SORT_3 SORT_MAKE_STR(bitonic_sort_3)
236static __inline void BITONIC_SORT_3(SORT_TYPE *dst) {
237 SORT_CSWAP(dst[1], dst[2]);
238 SORT_CSWAP(dst[0], dst[2]);
239 SORT_CSWAP(dst[0], dst[1]);
240}
241
242
243#define BITONIC_SORT_4 SORT_MAKE_STR(bitonic_sort_4)
244static __inline void BITONIC_SORT_4(SORT_TYPE *dst) {
245 SORT_CSWAP(dst[0], dst[1]);
246 SORT_CSWAP(dst[2], dst[3]);
247 SORT_CSWAP(dst[0], dst[2]);
248 SORT_CSWAP(dst[1], dst[3]);
249 SORT_CSWAP(dst[1], dst[2]);
250}
251
252
253#define BITONIC_SORT_5 SORT_MAKE_STR(bitonic_sort_5)
254static __inline void BITONIC_SORT_5(SORT_TYPE *dst) {
255 SORT_CSWAP(dst[0], dst[1]);
256 SORT_CSWAP(dst[3], dst[4]);
257 SORT_CSWAP(dst[2], dst[4]);
258 SORT_CSWAP(dst[2], dst[3]);
259 SORT_CSWAP(dst[1], dst[4]);
260 SORT_CSWAP(dst[0], dst[3]);
261 SORT_CSWAP(dst[0], dst[2]);
262 SORT_CSWAP(dst[1], dst[3]);
263 SORT_CSWAP(dst[1], dst[2]);
264}
265
266
267#define BITONIC_SORT_6 SORT_MAKE_STR(bitonic_sort_6)
268static __inline void BITONIC_SORT_6(SORT_TYPE *dst) {
269 SORT_CSWAP(dst[1], dst[2]);
270 SORT_CSWAP(dst[4], dst[5]);
271 SORT_CSWAP(dst[0], dst[2]);
272 SORT_CSWAP(dst[3], dst[5]);
273 SORT_CSWAP(dst[0], dst[1]);
274 SORT_CSWAP(dst[3], dst[4]);
275 SORT_CSWAP(dst[2], dst[5]);
276 SORT_CSWAP(dst[0], dst[3]);
277 SORT_CSWAP(dst[1], dst[4]);
278 SORT_CSWAP(dst[2], dst[4]);
279 SORT_CSWAP(dst[1], dst[3]);
280 SORT_CSWAP(dst[2], dst[3]);
281}
282
283
284#define BITONIC_SORT_7 SORT_MAKE_STR(bitonic_sort_7)
285static __inline void BITONIC_SORT_7(SORT_TYPE *dst) {
286 SORT_CSWAP(dst[1], dst[2]);
287 SORT_CSWAP(dst[3], dst[4]);
288 SORT_CSWAP(dst[5], dst[6]);
289 SORT_CSWAP(dst[0], dst[2]);
290 SORT_CSWAP(dst[3], dst[5]);
291 SORT_CSWAP(dst[4], dst[6]);
292 SORT_CSWAP(dst[0], dst[1]);
293 SORT_CSWAP(dst[4], dst[5]);
294 SORT_CSWAP(dst[2], dst[6]);
295 SORT_CSWAP(dst[0], dst[4]);
296 SORT_CSWAP(dst[1], dst[5]);
297 SORT_CSWAP(dst[0], dst[3]);
298 SORT_CSWAP(dst[2], dst[5]);
299 SORT_CSWAP(dst[1], dst[3]);
300 SORT_CSWAP(dst[2], dst[4]);
301 SORT_CSWAP(dst[2], dst[3]);
302}
303
304
305#define BITONIC_SORT_8 SORT_MAKE_STR(bitonic_sort_8)
306static __inline void BITONIC_SORT_8(SORT_TYPE *dst) {
307 SORT_CSWAP(dst[0], dst[1]);
308 SORT_CSWAP(dst[2], dst[3]);
309 SORT_CSWAP(dst[4], dst[5]);
310 SORT_CSWAP(dst[6], dst[7]);
311 SORT_CSWAP(dst[0], dst[2]);
312 SORT_CSWAP(dst[1], dst[3]);
313 SORT_CSWAP(dst[4], dst[6]);
314 SORT_CSWAP(dst[5], dst[7]);
315 SORT_CSWAP(dst[1], dst[2]);
316 SORT_CSWAP(dst[5], dst[6]);
317 SORT_CSWAP(dst[0], dst[4]);
318 SORT_CSWAP(dst[3], dst[7]);
319 SORT_CSWAP(dst[1], dst[5]);
320 SORT_CSWAP(dst[2], dst[6]);
321 SORT_CSWAP(dst[1], dst[4]);
322 SORT_CSWAP(dst[3], dst[6]);
323 SORT_CSWAP(dst[2], dst[4]);
324 SORT_CSWAP(dst[3], dst[5]);
325 SORT_CSWAP(dst[3], dst[4]);
326}
327
328
329#define BITONIC_SORT_9 SORT_MAKE_STR(bitonic_sort_9)
330static __inline void BITONIC_SORT_9(SORT_TYPE *dst) {
331 SORT_CSWAP(dst[0], dst[1]);
332 SORT_CSWAP(dst[3], dst[4]);
333 SORT_CSWAP(dst[6], dst[7]);
334 SORT_CSWAP(dst[1], dst[2]);
335 SORT_CSWAP(dst[4], dst[5]);
336 SORT_CSWAP(dst[7], dst[8]);
337 SORT_CSWAP(dst[0], dst[1]);
338 SORT_CSWAP(dst[3], dst[4]);
339 SORT_CSWAP(dst[6], dst[7]);
340 SORT_CSWAP(dst[2], dst[5]);
341 SORT_CSWAP(dst[0], dst[3]);
342 SORT_CSWAP(dst[1], dst[4]);
343 SORT_CSWAP(dst[5], dst[8]);
344 SORT_CSWAP(dst[3], dst[6]);
345 SORT_CSWAP(dst[4], dst[7]);
346 SORT_CSWAP(dst[2], dst[5]);
347 SORT_CSWAP(dst[0], dst[3]);
348 SORT_CSWAP(dst[1], dst[4]);
349 SORT_CSWAP(dst[5], dst[7]);
350 SORT_CSWAP(dst[2], dst[6]);
351 SORT_CSWAP(dst[1], dst[3]);
352 SORT_CSWAP(dst[4], dst[6]);
353 SORT_CSWAP(dst[2], dst[4]);
354 SORT_CSWAP(dst[5], dst[6]);
355 SORT_CSWAP(dst[2], dst[3]);
356}
357
358
359#define BITONIC_SORT_10 SORT_MAKE_STR(bitonic_sort_10)
360static __inline void BITONIC_SORT_10(SORT_TYPE *dst) {
361 SORT_CSWAP(dst[4], dst[9]);
362 SORT_CSWAP(dst[3], dst[8]);
363 SORT_CSWAP(dst[2], dst[7]);
364 SORT_CSWAP(dst[1], dst[6]);
365 SORT_CSWAP(dst[0], dst[5]);
366 SORT_CSWAP(dst[1], dst[4]);
367 SORT_CSWAP(dst[6], dst[9]);
368 SORT_CSWAP(dst[0], dst[3]);
369 SORT_CSWAP(dst[5], dst[8]);
370 SORT_CSWAP(dst[0], dst[2]);
371 SORT_CSWAP(dst[3], dst[6]);
372 SORT_CSWAP(dst[7], dst[9]);
373 SORT_CSWAP(dst[0], dst[1]);
374 SORT_CSWAP(dst[2], dst[4]);
375 SORT_CSWAP(dst[5], dst[7]);
376 SORT_CSWAP(dst[8], dst[9]);
377 SORT_CSWAP(dst[1], dst[2]);
378 SORT_CSWAP(dst[4], dst[6]);
379 SORT_CSWAP(dst[7], dst[8]);
380 SORT_CSWAP(dst[3], dst[5]);
381 SORT_CSWAP(dst[2], dst[5]);
382 SORT_CSWAP(dst[6], dst[8]);
383 SORT_CSWAP(dst[1], dst[3]);
384 SORT_CSWAP(dst[4], dst[7]);
385 SORT_CSWAP(dst[2], dst[3]);
386 SORT_CSWAP(dst[6], dst[7]);
387 SORT_CSWAP(dst[3], dst[4]);
388 SORT_CSWAP(dst[5], dst[6]);
389 SORT_CSWAP(dst[4], dst[5]);
390}
391
392
393#define BITONIC_SORT_11 SORT_MAKE_STR(bitonic_sort_11)
394static __inline void BITONIC_SORT_11(SORT_TYPE *dst) {
395 SORT_CSWAP(dst[0], dst[1]);
396 SORT_CSWAP(dst[2], dst[3]);
397 SORT_CSWAP(dst[4], dst[5]);
398 SORT_CSWAP(dst[6], dst[7]);
399 SORT_CSWAP(dst[8], dst[9]);
400 SORT_CSWAP(dst[1], dst[3]);
401 SORT_CSWAP(dst[5], dst[7]);
402 SORT_CSWAP(dst[0], dst[2]);
403 SORT_CSWAP(dst[4], dst[6]);
404 SORT_CSWAP(dst[8], dst[10]);
405 SORT_CSWAP(dst[1], dst[2]);
406 SORT_CSWAP(dst[5], dst[6]);
407 SORT_CSWAP(dst[9], dst[10]);
408 SORT_CSWAP(dst[0], dst[4]);
409 SORT_CSWAP(dst[3], dst[7]);
410 SORT_CSWAP(dst[1], dst[5]);
411 SORT_CSWAP(dst[6], dst[10]);
412 SORT_CSWAP(dst[4], dst[8]);
413 SORT_CSWAP(dst[5], dst[9]);
414 SORT_CSWAP(dst[2], dst[6]);
415 SORT_CSWAP(dst[0], dst[4]);
416 SORT_CSWAP(dst[3], dst[8]);
417 SORT_CSWAP(dst[1], dst[5]);
418 SORT_CSWAP(dst[6], dst[10]);
419 SORT_CSWAP(dst[2], dst[3]);
420 SORT_CSWAP(dst[8], dst[9]);
421 SORT_CSWAP(dst[1], dst[4]);
422 SORT_CSWAP(dst[7], dst[10]);
423 SORT_CSWAP(dst[3], dst[5]);
424 SORT_CSWAP(dst[6], dst[8]);
425 SORT_CSWAP(dst[2], dst[4]);
426 SORT_CSWAP(dst[7], dst[9]);
427 SORT_CSWAP(dst[5], dst[6]);
428 SORT_CSWAP(dst[3], dst[4]);
429 SORT_CSWAP(dst[7], dst[8]);
430}
431
432
433#define BITONIC_SORT_12 SORT_MAKE_STR(bitonic_sort_12)
434static __inline void BITONIC_SORT_12(SORT_TYPE *dst) {
435 SORT_CSWAP(dst[0], dst[1]);
436 SORT_CSWAP(dst[2], dst[3]);
437 SORT_CSWAP(dst[4], dst[5]);
438 SORT_CSWAP(dst[6], dst[7]);
439 SORT_CSWAP(dst[8], dst[9]);
440 SORT_CSWAP(dst[10], dst[11]);
441 SORT_CSWAP(dst[1], dst[3]);
442 SORT_CSWAP(dst[5], dst[7]);
443 SORT_CSWAP(dst[9], dst[11]);
444 SORT_CSWAP(dst[0], dst[2]);
445 SORT_CSWAP(dst[4], dst[6]);
446 SORT_CSWAP(dst[8], dst[10]);
447 SORT_CSWAP(dst[1], dst[2]);
448 SORT_CSWAP(dst[5], dst[6]);
449 SORT_CSWAP(dst[9], dst[10]);
450 SORT_CSWAP(dst[0], dst[4]);
451 SORT_CSWAP(dst[7], dst[11]);
452 SORT_CSWAP(dst[1], dst[5]);
453 SORT_CSWAP(dst[6], dst[10]);
454 SORT_CSWAP(dst[3], dst[7]);
455 SORT_CSWAP(dst[4], dst[8]);
456 SORT_CSWAP(dst[5], dst[9]);
457 SORT_CSWAP(dst[2], dst[6]);
458 SORT_CSWAP(dst[0], dst[4]);
459 SORT_CSWAP(dst[7], dst[11]);
460 SORT_CSWAP(dst[3], dst[8]);
461 SORT_CSWAP(dst[1], dst[5]);
462 SORT_CSWAP(dst[6], dst[10]);
463 SORT_CSWAP(dst[2], dst[3]);
464 SORT_CSWAP(dst[8], dst[9]);
465 SORT_CSWAP(dst[1], dst[4]);
466 SORT_CSWAP(dst[7], dst[10]);
467 SORT_CSWAP(dst[3], dst[5]);
468 SORT_CSWAP(dst[6], dst[8]);
469 SORT_CSWAP(dst[2], dst[4]);
470 SORT_CSWAP(dst[7], dst[9]);
471 SORT_CSWAP(dst[5], dst[6]);
472 SORT_CSWAP(dst[3], dst[4]);
473 SORT_CSWAP(dst[7], dst[8]);
474}
475
476
477#define BITONIC_SORT_13 SORT_MAKE_STR(bitonic_sort_13)
478static __inline void BITONIC_SORT_13(SORT_TYPE *dst) {
479 SORT_CSWAP(dst[1], dst[7]);
480 SORT_CSWAP(dst[9], dst[11]);
481 SORT_CSWAP(dst[3], dst[4]);
482 SORT_CSWAP(dst[5], dst[8]);
483 SORT_CSWAP(dst[0], dst[12]);
484 SORT_CSWAP(dst[2], dst[6]);
485 SORT_CSWAP(dst[0], dst[1]);
486 SORT_CSWAP(dst[2], dst[3]);
487 SORT_CSWAP(dst[4], dst[6]);
488 SORT_CSWAP(dst[8], dst[11]);
489 SORT_CSWAP(dst[7], dst[12]);
490 SORT_CSWAP(dst[5], dst[9]);
491 SORT_CSWAP(dst[0], dst[2]);
492 SORT_CSWAP(dst[3], dst[7]);
493 SORT_CSWAP(dst[10], dst[11]);
494 SORT_CSWAP(dst[1], dst[4]);
495 SORT_CSWAP(dst[6], dst[12]);
496 SORT_CSWAP(dst[7], dst[8]);
497 SORT_CSWAP(dst[11], dst[12]);
498 SORT_CSWAP(dst[4], dst[9]);
499 SORT_CSWAP(dst[6], dst[10]);
500 SORT_CSWAP(dst[3], dst[4]);
501 SORT_CSWAP(dst[5], dst[6]);
502 SORT_CSWAP(dst[8], dst[9]);
503 SORT_CSWAP(dst[10], dst[11]);
504 SORT_CSWAP(dst[1], dst[7]);
505 SORT_CSWAP(dst[2], dst[6]);
506 SORT_CSWAP(dst[9], dst[11]);
507 SORT_CSWAP(dst[1], dst[3]);
508 SORT_CSWAP(dst[4], dst[7]);
509 SORT_CSWAP(dst[8], dst[10]);
510 SORT_CSWAP(dst[0], dst[5]);
511 SORT_CSWAP(dst[2], dst[5]);
512 SORT_CSWAP(dst[6], dst[8]);
513 SORT_CSWAP(dst[9], dst[10]);
514 SORT_CSWAP(dst[1], dst[2]);
515 SORT_CSWAP(dst[3], dst[5]);
516 SORT_CSWAP(dst[7], dst[8]);
517 SORT_CSWAP(dst[4], dst[6]);
518 SORT_CSWAP(dst[2], dst[3]);
519 SORT_CSWAP(dst[4], dst[5]);
520 SORT_CSWAP(dst[6], dst[7]);
521 SORT_CSWAP(dst[8], dst[9]);
522 SORT_CSWAP(dst[3], dst[4]);
523 SORT_CSWAP(dst[5], dst[6]);
524}
525
526
527#define BITONIC_SORT_14 SORT_MAKE_STR(bitonic_sort_14)
528static __inline void BITONIC_SORT_14(SORT_TYPE *dst) {
529 SORT_CSWAP(dst[0], dst[1]);
530 SORT_CSWAP(dst[2], dst[3]);
531 SORT_CSWAP(dst[4], dst[5]);
532 SORT_CSWAP(dst[6], dst[7]);
533 SORT_CSWAP(dst[8], dst[9]);
534 SORT_CSWAP(dst[10], dst[11]);
535 SORT_CSWAP(dst[12], dst[13]);
536 SORT_CSWAP(dst[0], dst[2]);
537 SORT_CSWAP(dst[4], dst[6]);
538 SORT_CSWAP(dst[8], dst[10]);
539 SORT_CSWAP(dst[1], dst[3]);
540 SORT_CSWAP(dst[5], dst[7]);
541 SORT_CSWAP(dst[9], dst[11]);
542 SORT_CSWAP(dst[0], dst[4]);
543 SORT_CSWAP(dst[8], dst[12]);
544 SORT_CSWAP(dst[1], dst[5]);
545 SORT_CSWAP(dst[9], dst[13]);
546 SORT_CSWAP(dst[2], dst[6]);
547 SORT_CSWAP(dst[3], dst[7]);
548 SORT_CSWAP(dst[0], dst[8]);
549 SORT_CSWAP(dst[1], dst[9]);
550 SORT_CSWAP(dst[2], dst[10]);
551 SORT_CSWAP(dst[3], dst[11]);
552 SORT_CSWAP(dst[4], dst[12]);
553 SORT_CSWAP(dst[5], dst[13]);
554 SORT_CSWAP(dst[5], dst[10]);
555 SORT_CSWAP(dst[6], dst[9]);
556 SORT_CSWAP(dst[3], dst[12]);
557 SORT_CSWAP(dst[7], dst[11]);
558 SORT_CSWAP(dst[1], dst[2]);
559 SORT_CSWAP(dst[4], dst[8]);
560 SORT_CSWAP(dst[1], dst[4]);
561 SORT_CSWAP(dst[7], dst[13]);
562 SORT_CSWAP(dst[2], dst[8]);
563 SORT_CSWAP(dst[5], dst[6]);
564 SORT_CSWAP(dst[9], dst[10]);
565 SORT_CSWAP(dst[2], dst[4]);
566 SORT_CSWAP(dst[11], dst[13]);
567 SORT_CSWAP(dst[3], dst[8]);
568 SORT_CSWAP(dst[7], dst[12]);
569 SORT_CSWAP(dst[6], dst[8]);
570 SORT_CSWAP(dst[10], dst[12]);
571 SORT_CSWAP(dst[3], dst[5]);
572 SORT_CSWAP(dst[7], dst[9]);
573 SORT_CSWAP(dst[3], dst[4]);
574 SORT_CSWAP(dst[5], dst[6]);
575 SORT_CSWAP(dst[7], dst[8]);
576 SORT_CSWAP(dst[9], dst[10]);
577 SORT_CSWAP(dst[11], dst[12]);
578 SORT_CSWAP(dst[6], dst[7]);
579 SORT_CSWAP(dst[8], dst[9]);
580}
581
582
583#define BITONIC_SORT_15 SORT_MAKE_STR(bitonic_sort_15)
584static __inline void BITONIC_SORT_15(SORT_TYPE *dst) {
585 SORT_CSWAP(dst[0], dst[1]);
586 SORT_CSWAP(dst[2], dst[3]);
587 SORT_CSWAP(dst[4], dst[5]);
588 SORT_CSWAP(dst[6], dst[7]);
589 SORT_CSWAP(dst[8], dst[9]);
590 SORT_CSWAP(dst[10], dst[11]);
591 SORT_CSWAP(dst[12], dst[13]);
592 SORT_CSWAP(dst[0], dst[2]);
593 SORT_CSWAP(dst[4], dst[6]);
594 SORT_CSWAP(dst[8], dst[10]);
595 SORT_CSWAP(dst[12], dst[14]);
596 SORT_CSWAP(dst[1], dst[3]);
597 SORT_CSWAP(dst[5], dst[7]);
598 SORT_CSWAP(dst[9], dst[11]);
599 SORT_CSWAP(dst[0], dst[4]);
600 SORT_CSWAP(dst[8], dst[12]);
601 SORT_CSWAP(dst[1], dst[5]);
602 SORT_CSWAP(dst[9], dst[13]);
603 SORT_CSWAP(dst[2], dst[6]);
604 SORT_CSWAP(dst[10], dst[14]);
605 SORT_CSWAP(dst[3], dst[7]);
606 SORT_CSWAP(dst[0], dst[8]);
607 SORT_CSWAP(dst[1], dst[9]);
608 SORT_CSWAP(dst[2], dst[10]);
609 SORT_CSWAP(dst[3], dst[11]);
610 SORT_CSWAP(dst[4], dst[12]);
611 SORT_CSWAP(dst[5], dst[13]);
612 SORT_CSWAP(dst[6], dst[14]);
613 SORT_CSWAP(dst[5], dst[10]);
614 SORT_CSWAP(dst[6], dst[9]);
615 SORT_CSWAP(dst[3], dst[12]);
616 SORT_CSWAP(dst[13], dst[14]);
617 SORT_CSWAP(dst[7], dst[11]);
618 SORT_CSWAP(dst[1], dst[2]);
619 SORT_CSWAP(dst[4], dst[8]);
620 SORT_CSWAP(dst[1], dst[4]);
621 SORT_CSWAP(dst[7], dst[13]);
622 SORT_CSWAP(dst[2], dst[8]);
623 SORT_CSWAP(dst[11], dst[14]);
624 SORT_CSWAP(dst[5], dst[6]);
625 SORT_CSWAP(dst[9], dst[10]);
626 SORT_CSWAP(dst[2], dst[4]);
627 SORT_CSWAP(dst[11], dst[13]);
628 SORT_CSWAP(dst[3], dst[8]);
629 SORT_CSWAP(dst[7], dst[12]);
630 SORT_CSWAP(dst[6], dst[8]);
631 SORT_CSWAP(dst[10], dst[12]);
632 SORT_CSWAP(dst[3], dst[5]);
633 SORT_CSWAP(dst[7], dst[9]);
634 SORT_CSWAP(dst[3], dst[4]);
635 SORT_CSWAP(dst[5], dst[6]);
636 SORT_CSWAP(dst[7], dst[8]);
637 SORT_CSWAP(dst[9], dst[10]);
638 SORT_CSWAP(dst[11], dst[12]);
639 SORT_CSWAP(dst[6], dst[7]);
640 SORT_CSWAP(dst[8], dst[9]);
641}
642
643
644#define BITONIC_SORT_16 SORT_MAKE_STR(bitonic_sort_16)
645static __inline void BITONIC_SORT_16(SORT_TYPE *dst) {
646 SORT_CSWAP(dst[0], dst[1]);
647 SORT_CSWAP(dst[2], dst[3]);
648 SORT_CSWAP(dst[4], dst[5]);
649 SORT_CSWAP(dst[6], dst[7]);
650 SORT_CSWAP(dst[8], dst[9]);
651 SORT_CSWAP(dst[10], dst[11]);
652 SORT_CSWAP(dst[12], dst[13]);
653 SORT_CSWAP(dst[14], dst[15]);
654 SORT_CSWAP(dst[0], dst[2]);
655 SORT_CSWAP(dst[4], dst[6]);
656 SORT_CSWAP(dst[8], dst[10]);
657 SORT_CSWAP(dst[12], dst[14]);
658 SORT_CSWAP(dst[1], dst[3]);
659 SORT_CSWAP(dst[5], dst[7]);
660 SORT_CSWAP(dst[9], dst[11]);
661 SORT_CSWAP(dst[13], dst[15]);
662 SORT_CSWAP(dst[0], dst[4]);
663 SORT_CSWAP(dst[8], dst[12]);
664 SORT_CSWAP(dst[1], dst[5]);
665 SORT_CSWAP(dst[9], dst[13]);
666 SORT_CSWAP(dst[2], dst[6]);
667 SORT_CSWAP(dst[10], dst[14]);
668 SORT_CSWAP(dst[3], dst[7]);
669 SORT_CSWAP(dst[11], dst[15]);
670 SORT_CSWAP(dst[0], dst[8]);
671 SORT_CSWAP(dst[1], dst[9]);
672 SORT_CSWAP(dst[2], dst[10]);
673 SORT_CSWAP(dst[3], dst[11]);
674 SORT_CSWAP(dst[4], dst[12]);
675 SORT_CSWAP(dst[5], dst[13]);
676 SORT_CSWAP(dst[6], dst[14]);
677 SORT_CSWAP(dst[7], dst[15]);
678 SORT_CSWAP(dst[5], dst[10]);
679 SORT_CSWAP(dst[6], dst[9]);
680 SORT_CSWAP(dst[3], dst[12]);
681 SORT_CSWAP(dst[13], dst[14]);
682 SORT_CSWAP(dst[7], dst[11]);
683 SORT_CSWAP(dst[1], dst[2]);
684 SORT_CSWAP(dst[4], dst[8]);
685 SORT_CSWAP(dst[1], dst[4]);
686 SORT_CSWAP(dst[7], dst[13]);
687 SORT_CSWAP(dst[2], dst[8]);
688 SORT_CSWAP(dst[11], dst[14]);
689 SORT_CSWAP(dst[5], dst[6]);
690 SORT_CSWAP(dst[9], dst[10]);
691 SORT_CSWAP(dst[2], dst[4]);
692 SORT_CSWAP(dst[11], dst[13]);
693 SORT_CSWAP(dst[3], dst[8]);
694 SORT_CSWAP(dst[7], dst[12]);
695 SORT_CSWAP(dst[6], dst[8]);
696 SORT_CSWAP(dst[10], dst[12]);
697 SORT_CSWAP(dst[3], dst[5]);
698 SORT_CSWAP(dst[7], dst[9]);
699 SORT_CSWAP(dst[3], dst[4]);
700 SORT_CSWAP(dst[5], dst[6]);
701 SORT_CSWAP(dst[7], dst[8]);
702 SORT_CSWAP(dst[9], dst[10]);
703 SORT_CSWAP(dst[11], dst[12]);
704 SORT_CSWAP(dst[6], dst[7]);
705 SORT_CSWAP(dst[8], dst[9]);
706}
707
708SORT_DEF void BITONIC_SORT(SORT_TYPE *dst, const size_t size) {
709 switch (size) {
710 case 0:
711 case 1:
712 break;
713
714 case 2:
715 BITONIC_SORT_2(dst);
716 break;
717
718 case 3:
719 BITONIC_SORT_3(dst);
720 break;
721
722 case 4:
723 BITONIC_SORT_4(dst);
724 break;
725
726 case 5:
727 BITONIC_SORT_5(dst);
728 break;
729
730 case 6:
731 BITONIC_SORT_6(dst);
732 break;
733
734 case 7:
735 BITONIC_SORT_7(dst);
736 break;
737
738 case 8:
739 BITONIC_SORT_8(dst);
740 break;
741
742 case 9:
743 BITONIC_SORT_9(dst);
744 break;
745
746 case 10:
747 BITONIC_SORT_10(dst);
748 break;
749
750 case 11:
751 BITONIC_SORT_11(dst);
752 break;
753
754 case 12:
755 BITONIC_SORT_12(dst);
756 break;
757
758 case 13:
759 BITONIC_SORT_13(dst);
760 break;
761
762 case 14:
763 BITONIC_SORT_14(dst);
764 break;
765
766 case 15:
767 BITONIC_SORT_15(dst);
768 break;
769
770 case 16:
771 BITONIC_SORT_16(dst);
772 break;
773
774 default:
775 BINARY_INSERTION_SORT(dst, size);
776 }
777}
778
779#if SORT_SAFE_CPY
780
781SORT_DEF void SORT_TYPE_CPY(SORT_TYPE *dst, SORT_TYPE *src, const size_t size) {
782 size_t i = 0;
783
784 for (; i < size; ++i) {
785 dst[i] = src[i];
786 }
787}
788
789SORT_DEF void SORT_TYPE_MOVE(SORT_TYPE *dst, SORT_TYPE *src, const size_t size) {
790 size_t i;
791
792 if (dst < src) {
793 SORT_TYPE_CPY(dst, src, size);
794 } else if (dst != src && size > 0) {
795 for (i = size - 1; i > 0; --i) {
796 dst[i] = src[i];
797 }
798
799 *dst = *src;
800 }
801}
802
803#else
804
805#undef SORT_TYPE_CPY
806#define SORT_TYPE_CPY(dst, src, size) memcpy((dst), (src), (size) * sizeof(SORT_TYPE))
807#undef SORT_TYPE_MOVE
808#define SORT_TYPE_MOVE(dst, src, size) memmove((dst), (src), (size) * sizeof(SORT_TYPE))
809
810#endif
811
812SORT_DEF SORT_TYPE* SORT_NEW_BUFFER(size_t size) {
813#if SORT_SAFE_CPY
814 return new SORT_TYPE[size];
815#else
816 return (SORT_TYPE*)malloc(size * sizeof(SORT_TYPE));
817#endif
818}
819
820SORT_DEF void SORT_DELETE_BUFFER(SORT_TYPE* pointer) {
821#if SORT_SAFE_CPY
822 delete[] pointer;
823#else
824 free(pointer);
825#endif
826}
827
828
829/* Shell sort implementation based on Wikipedia article
830 http://en.wikipedia.org/wiki/Shell_sort
831*/
832SORT_DEF void SHELL_SORT(SORT_TYPE *dst, const size_t size) {
833 /* don't bother sorting an array of size 0 or 1 */
834 /* TODO: binary search to find first gap? */
835 int inci = 47;
836 size_t inc = shell_gaps[inci];
837 size_t i;
838
839 if (size <= 1) {
840 return;
841 }
842
843 while (inc > (size >> 1)) {
844 inc = shell_gaps[--inci];
845 }
846
847 while (1) {
848 for (i = inc; i < size; i++) {
849 SORT_TYPE temp = dst[i];
850 size_t j = i;
851
852 while ((j >= inc) && (SORT_CMP(dst[j - inc], temp) > 0)) {
853 dst[j] = dst[j - inc];
854 j -= inc;
855 }
856
857 dst[j] = temp;
858 }
859
860 if (inc == 1) {
861 break;
862 }
863
864 inc = shell_gaps[--inci];
865 }
866}
867
868/* Function used to do a binary search for binary insertion sort */
869static __inline size_t BINARY_INSERTION_FIND(SORT_TYPE *dst, const SORT_TYPE x,
870 const size_t size) {
871 size_t l, c, r;
872 SORT_TYPE cx;
873 l = 0;
874 r = size - 1;
875 c = r >> 1;
876
877 /* check for out of bounds at the beginning. */
878 if (SORT_CMP(x, dst[0]) < 0) {
879 return 0;
880 } else if (SORT_CMP(x, dst[r]) > 0) {
881 return r;
882 }
883
884 cx = dst[c];
885
886 while (1) {
887 const int val = SORT_CMP(x, cx);
888
889 if (val < 0) {
890 if (c - l <= 1) {
891 return c;
892 }
893
894 r = c;
895 } else { /* allow = for stability. The binary search favors the right. */
896 if (r - c <= 1) {
897 return c + 1;
898 }
899
900 l = c;
901 }
902
903 c = l + ((r - l) >> 1);
904 cx = dst[c];
905 }
906}
907
908/* Binary insertion sort, but knowing that the first "start" entries are sorted. Used in timsort. */
909static void BINARY_INSERTION_SORT_START(SORT_TYPE *dst, const size_t start, const size_t size) {
910 size_t i;
911
912 for (i = start; i < size; i++) {
913 size_t j;
914 SORT_TYPE x;
915 size_t location;
916
917 /* If this entry is already correct, just move along */
918 if (SORT_CMP(dst[i - 1], dst[i]) <= 0) {
919 continue;
920 }
921
922 /* Else we need to find the right place, shift everything over, and squeeze in */
923 x = dst[i];
924 location = BINARY_INSERTION_FIND(dst, x, i);
925
926 for (j = i - 1; j >= location; j--) {
927 dst[j + 1] = dst[j];
928
929 if (j == 0) { /* check edge case because j is unsigned */
930 break;
931 }
932 }
933
934 dst[location] = x;
935 }
936}
937
938/* Binary insertion sort */
939SORT_DEF void BINARY_INSERTION_SORT(SORT_TYPE *dst, const size_t size) {
940 /* don't bother sorting an array of size <= 1 */
941 if (size <= 1) {
942 return;
943 }
944
945 BINARY_INSERTION_SORT_START(dst, 1, size);
946}
947
948/* In-place mergesort */
949SORT_DEF void MERGE_SORT_IN_PLACE_ASWAP(SORT_TYPE * dst1, SORT_TYPE * dst2, size_t len) {
950 do {
951 SORT_SWAP(*dst1, *dst2);
952 dst1++;
953 dst2++;
954 } while (--len);
955}
956
957SORT_DEF void MERGE_SORT_IN_PLACE_FRONTMERGE(SORT_TYPE *dst1, size_t l1, SORT_TYPE *dst2,
958 size_t l2) {
959 SORT_TYPE *dst0 = dst2 - l1;
960
961 if (SORT_CMP(dst1[l1 - 1], dst2[0]) <= 0) {
962 MERGE_SORT_IN_PLACE_ASWAP(dst1, dst0, l1);
963 return;
964 }
965
966 do {
967 while (SORT_CMP(*dst2, *dst1) > 0) {
968 SORT_SWAP(*dst1, *dst0);
969 dst1++;
970 dst0++;
971
972 if (--l1 == 0) {
973 return;
974 }
975 }
976
977 SORT_SWAP(*dst2, *dst0);
978 dst2++;
979 dst0++;
980 } while (--l2);
981
982 do {
983 SORT_SWAP(*dst1, *dst0);
984 dst1++;
985 dst0++;
986 } while (--l1);
987}
988
989SORT_DEF size_t MERGE_SORT_IN_PLACE_BACKMERGE(SORT_TYPE * dst1, size_t l1, SORT_TYPE * dst2,
990 size_t l2) {
991 size_t res;
992 SORT_TYPE *dst0 = dst2 + l1;
993
994 if (SORT_CMP(dst1[1 - l1], dst2[0]) >= 0) {
995 MERGE_SORT_IN_PLACE_ASWAP(dst1 - l1 + 1, dst0 - l1 + 1, l1);
996 return l1;
997 }
998
999 do {
1000 while (SORT_CMP(*dst2, *dst1) < 0) {
1001 SORT_SWAP(*dst1, *dst0);
1002 dst1--;
1003 dst0--;
1004
1005 if (--l1 == 0) {
1006 return 0;
1007 }
1008 }
1009
1010 SORT_SWAP(*dst2, *dst0);
1011 dst2--;
1012 dst0--;
1013 } while (--l2);
1014
1015 res = l1;
1016
1017 do {
1018 SORT_SWAP(*dst1, *dst0);
1019 dst1--;
1020 dst0--;
1021 } while (--l1);
1022
1023 return res;
1024}
1025
1026/* merge dst[p0..p1) by buffer dst[p1..p1+r) */
1027SORT_DEF void MERGE_SORT_IN_PLACE_RMERGE(SORT_TYPE *dst, size_t len, size_t lp, size_t r) {
1028 size_t i, lq;
1029 int cv;
1030
1031 if (SORT_CMP(dst[lp], dst[lp - 1]) >= 0) {
1032 return;
1033 }
1034
1035 lq = lp;
1036
1037 for (i = 0; i < len; i += r) {
1038 /* select smallest dst[p0+n*r] */
1039 size_t q = i, j;
1040
1041 for (j = lp; j <= lq; j += r) {
1042 cv = SORT_CMP(dst[j], dst[q]);
1043
1044 if (cv == 0) {
1045 cv = SORT_CMP(dst[j + r - 1], dst[q + r - 1]);
1046 }
1047
1048 if (cv < 0) {
1049 q = j;
1050 }
1051 }
1052
1053 if (q != i) {
1054 MERGE_SORT_IN_PLACE_ASWAP(dst + i, dst + q, r); /* swap it with current position */
1055
1056 if (q == lq && q < (len - r)) {
1057 lq += r;
1058 }
1059 }
1060
1061 if (i != 0 && SORT_CMP(dst[i], dst[i - 1]) < 0) {
1062 MERGE_SORT_IN_PLACE_ASWAP(dst + len, dst + i, r); /* swap current position with buffer */
1063 MERGE_SORT_IN_PLACE_BACKMERGE(dst + (len + r - 1), r, dst + (i - 1),
1064 r); /* buffer :merge: dst[i-r..i) -> dst[i-r..i+r) */
1065 }
1066
1067 if (lp == i) {
1068 lp += r;
1069 }
1070 }
1071}
1072
1073/* In-place Merge Sort implementation. (c)2012, Andrey Astrelin, astrelin@tochka.ru */
1074SORT_DEF void MERGE_SORT_IN_PLACE(SORT_TYPE *dst, const size_t len) {
1075 /* don't bother sorting an array of size <= 1 */
1076 size_t r = rbnd(len);
1077 size_t lr = (len / r - 1) * r;
1078 SORT_TYPE *dst1 = dst - 1;
1079 size_t p, m, q, q1, p0;
1080
1081 if (len <= 1) {
1082 return;
1083 }
1084
1085 if (len <= SMALL_SORT_BND) {
1086 SMALL_SORT(dst, len);
1087 return;
1088 }
1089
1090 for (p = 2; p <= lr; p += 2) {
1091 dst1 += 2;
1092
1093 if (SORT_CMP(dst1[0], dst1[-1]) < 0) {
1094 SORT_SWAP(dst1[0], dst1[-1]);
1095 }
1096
1097 if (p & 2) {
1098 continue;
1099 }
1100
1101 m = len - p;
1102 q = 2;
1103
1104 while ((p & q) == 0) {
1105 if (SORT_CMP(dst1[1 - q], dst1[-(int) q]) < 0) {
1106 break;
1107 }
1108
1109 q *= 2;
1110 }
1111
1112 if (p & q) {
1113 continue;
1114 }
1115
1116 if (q < m) {
1117 p0 = len - q;
1118 MERGE_SORT_IN_PLACE_ASWAP(dst + p - q, dst + p0, q);
1119
1120 for (;;) {
1121 q1 = 2 * q;
1122
1123 if ((q1 > m) || (p & q1)) {
1124 break;
1125 }
1126
1127 p0 = len - q1;
1128 MERGE_SORT_IN_PLACE_FRONTMERGE(dst + (p - q1), q, dst + p0 + q, q);
1129 q = q1;
1130 }
1131
1132 MERGE_SORT_IN_PLACE_BACKMERGE(dst + (len - 1), q, dst1 - q, q);
1133 q *= 2;
1134 }
1135
1136 q1 = q;
1137
1138 while (q1 > m) {
1139 q1 /= 2;
1140 }
1141
1142 while ((q & p) == 0) {
1143 q *= 2;
1144 MERGE_SORT_IN_PLACE_RMERGE(dst + (p - q), q, q / 2, q1);
1145 }
1146 }
1147
1148 q1 = 0;
1149
1150 for (q = r; q < lr; q *= 2) {
1151 if ((lr & q) != 0) {
1152 q1 += q;
1153
1154 if (q1 != q) {
1155 MERGE_SORT_IN_PLACE_RMERGE(dst + (lr - q1), q1, q, r);
1156 }
1157 }
1158 }
1159
1160 m = len - lr;
1161 MERGE_SORT_IN_PLACE(dst + lr, m);
1162 MERGE_SORT_IN_PLACE_ASWAP(dst, dst + lr, m);
1163 m += MERGE_SORT_IN_PLACE_BACKMERGE(dst + (m - 1), m, dst + (lr - 1), lr - m);
1164 MERGE_SORT_IN_PLACE(dst, m);
1165}
1166
1167/* Standard merge sort */
1168SORT_DEF void MERGE_SORT_RECURSIVE(SORT_TYPE *newdst, SORT_TYPE *dst, const size_t size) {
1169 const size_t middle = size / 2;
1170 size_t out = 0;
1171 size_t i = 0;
1172 size_t j = middle;
1173
1174 /* don't bother sorting an array of size <= 1 */
1175 if (size <= 1) {
1176 return;
1177 }
1178
1179 if (size <= SMALL_SORT_BND) {
1180 SMALL_STABLE_SORT(dst, size);
1181 return;
1182 }
1183
1184 MERGE_SORT_RECURSIVE(newdst, dst, middle);
1185 MERGE_SORT_RECURSIVE(newdst, &dst[middle], size - middle);
1186
1187 while (out != size) {
1188 if (i < middle) {
1189 if (j < size) {
1190 if (SORT_CMP(dst[i], dst[j]) <= 0) {
1191 newdst[out] = dst[i++];
1192 } else {
1193 newdst[out] = dst[j++];
1194 }
1195 } else {
1196 newdst[out] = dst[i++];
1197 }
1198 } else {
1199 newdst[out] = dst[j++];
1200 }
1201
1202 out++;
1203 }
1204
1205 SORT_TYPE_CPY(dst, newdst, size);
1206}
1207
1208/* Standard merge sort */
1209SORT_DEF void MERGE_SORT(SORT_TYPE *dst, const size_t size) {
1210 SORT_TYPE *newdst;
1211
1212 /* don't bother sorting an array of size <= 1 */
1213 if (size <= 1) {
1214 return;
1215 }
1216
1217 if (size <= SMALL_SORT_BND) {
1218 SMALL_STABLE_SORT(dst, size);
1219 return;
1220 }
1221
1222 newdst = SORT_NEW_BUFFER(size);
1223 MERGE_SORT_RECURSIVE(newdst, dst, size);
1224 SORT_DELETE_BUFFER(newdst);
1225}
1226
1227
1228static __inline size_t QUICK_SORT_PARTITION(SORT_TYPE *dst, const size_t left,
1229 const size_t right, const size_t pivot) {
1230 SORT_TYPE value = dst[pivot];
1231 size_t index = left;
1232 size_t i;
1233 int not_all_same = 0;
1234 /* move the pivot to the right */
1235 SORT_SWAP(dst[pivot], dst[right]);
1236
1237 for (i = left; i < right; i++) {
1238 int cmp = SORT_CMP(dst[i], value);
1239 /* check if everything is all the same */
1240 not_all_same |= cmp;
1241
1242 if (cmp < 0) {
1243 SORT_SWAP(dst[i], dst[index]);
1244 index++;
1245 }
1246 }
1247
1248 SORT_SWAP(dst[right], dst[index]);
1249
1250 /* avoid degenerate case */
1251 if (not_all_same == 0) {
1252 return SIZE_MAX;
1253 }
1254
1255 return index;
1256}
1257
1258/* Based on Knuth vol. 3
1259static __inline size_t QUICK_SORT_HOARE_PARTITION(SORT_TYPE *dst, const size_t l,
1260 const size_t r, const size_t pivot) {
1261 SORT_TYPE value;
1262 size_t i = l + 1;
1263 size_t j = r;
1264
1265 if (pivot != l) {
1266 SORT_SWAP(dst[pivot], dst[l]);
1267 }
1268 value = dst[l];
1269
1270 while (1) {
1271 while (SORT_CMP(dst[i], value) < 0) {
1272 i++;
1273 }
1274 while (SORT_CMP(value, dst[j]) < 0) {
1275 j--;
1276 }
1277 if (j <= i) {
1278 SORT_SWAP(dst[l], dst[j]);
1279 return j;
1280 }
1281 SORT_SWAP(dst[i], dst[j]);
1282 i++;
1283 j--;
1284 }
1285 return 0;
1286}
1287*/
1288
1289
1290/* Return the median index of the objects at the three indices. */
1291static __inline size_t MEDIAN(const SORT_TYPE *dst, const size_t a, const size_t b,
1292 const size_t c) {
1293 const int AB = SORT_CMP(dst[a], dst[b]) < 0;
1294
1295 if (AB) {
1296 /* a < b */
1297 const int BC = SORT_CMP(dst[b], dst[c]) < 0;
1298
1299 if (BC) {
1300 /* a < b < c */
1301 return b;
1302 } else {
1303 /* a < b, c < b */
1304 const int AC = SORT_CMP(dst[a], dst[c]) < 0;
1305
1306 if (AC) {
1307 /* a < c < b */
1308 return c;
1309 } else {
1310 /* c < a < b */
1311 return a;
1312 }
1313 }
1314 } else {
1315 /* b < a */
1316 const int AC = SORT_CMP(dst[a], dst[b]) < 0;
1317
1318 if (AC) {
1319 /* b < a < c */
1320 return a;
1321 } else {
1322 /* b < a, c < a */
1323 const int BC = SORT_CMP(dst[b], dst[c]) < 0;
1324
1325 if (BC) {
1326 /* b < c < a */
1327 return c;
1328 } else {
1329 /* c < b < a */
1330 return b;
1331 }
1332 }
1333 }
1334}
1335
1336static void QUICK_SORT_RECURSIVE(SORT_TYPE *dst, const size_t original_left,
1337 const size_t original_right) {
1338 size_t left;
1339 size_t right;
1340 size_t pivot;
1341 size_t new_pivot;
1342 size_t middle;
1343 int loop_count = 0;
1344 const int max_loops = 64 - CLZ(original_right - original_left); /* ~lg N */
1345 left = original_left;
1346 right = original_right;
1347
1348 while (1) {
1349 if (right <= left) {
1350 return;
1351 }
1352
1353 if ((right - left + 1U) <= SMALL_SORT_BND) {
1354 SMALL_SORT(&dst[left], right - left + 1U);
1355 return;
1356 }
1357
1358 if (++loop_count >= max_loops) {
1359 /* we have recursed / looped too many times; switch to heap sort */
1360 HEAP_SORT(&dst[left], right - left + 1U);
1361 return;
1362 }
1363
1364 /* median of 5 */
1365 middle = left + ((right - left) >> 1);
1366 pivot = MEDIAN((const SORT_TYPE *) dst, left, middle, right);
1367 pivot = MEDIAN((const SORT_TYPE *) dst, left + ((middle - left) >> 1), pivot,
1368 middle + ((right - middle) >> 1));
1369 new_pivot = QUICK_SORT_PARTITION(dst, left, right, pivot);
1370
1371 /* check for partition all equal */
1372 if (new_pivot == SIZE_MAX) {
1373 return;
1374 }
1375
1376 /* recurse only on the small part to avoid degenerate stack sizes */
1377 /* and manually do tail call on the large part */
1378 if (new_pivot - 1U - left > right - new_pivot - 1U) {
1379 /* left is bigger than right */
1380 QUICK_SORT_RECURSIVE(dst, new_pivot + 1U, right);
1381 /* tail call for left */
1382 right = new_pivot - 1U;
1383 } else {
1384 /* right is bigger than left */
1385 QUICK_SORT_RECURSIVE(dst, left, new_pivot - 1U);
1386 /* tail call for right */
1387 left = new_pivot + 1U;
1388 }
1389 }
1390}
1391
1392void QUICK_SORT(SORT_TYPE *dst, const size_t size) {
1393 /* don't bother sorting an array of size 1 */
1394 if (size <= 1) {
1395 return;
1396 }
1397
1398 QUICK_SORT_RECURSIVE(dst, 0U, size - 1U);
1399}
1400
1401
1402/* timsort implementation, based on timsort.txt */
1403
1404static __inline void REVERSE_ELEMENTS(SORT_TYPE *dst, size_t start, size_t end) {
1405 while (1) {
1406 if (start >= end) {
1407 return;
1408 }
1409
1410 SORT_SWAP(dst[start], dst[end]);
1411 start++;
1412 end--;
1413 }
1414}
1415
1416static size_t COUNT_RUN(SORT_TYPE *dst, const size_t start, const size_t size) {
1417 size_t curr;
1418
1419 if (size - start == 1) {
1420 return 1;
1421 }
1422
1423 if (start >= size - 2) {
1424 if (SORT_CMP(dst[size - 2], dst[size - 1]) > 0) {
1425 SORT_SWAP(dst[size - 2], dst[size - 1]);
1426 }
1427
1428 return 2;
1429 }
1430
1431 curr = start + 2;
1432
1433 if (SORT_CMP(dst[start], dst[start + 1]) <= 0) {
1434 /* increasing run */
1435 while (1) {
1436 if (curr == size - 1) {
1437 break;
1438 }
1439
1440 if (SORT_CMP(dst[curr - 1], dst[curr]) > 0) {
1441 break;
1442 }
1443
1444 curr++;
1445 }
1446
1447 return curr - start;
1448 } else {
1449 /* decreasing run */
1450 while (1) {
1451 if (curr == size - 1) {
1452 break;
1453 }
1454
1455 if (SORT_CMP(dst[curr - 1], dst[curr]) <= 0) {
1456 break;
1457 }
1458
1459 curr++;
1460 }
1461
1462 /* reverse in-place */
1463 REVERSE_ELEMENTS(dst, start, curr - 1);
1464 return curr - start;
1465 }
1466}
1467
1468static int CHECK_INVARIANT(TIM_SORT_RUN_T *stack, const int stack_curr) {
1469 size_t A, B, C;
1470
1471 if (stack_curr < 2) {
1472 return 1;
1473 }
1474
1475 if (stack_curr == 2) {
1476 const size_t A1 = stack[stack_curr - 2].length;
1477 const size_t B1 = stack[stack_curr - 1].length;
1478
1479 if (A1 <= B1) {
1480 return 0;
1481 }
1482
1483 return 1;
1484 }
1485
1486 A = stack[stack_curr - 3].length;
1487 B = stack[stack_curr - 2].length;
1488 C = stack[stack_curr - 1].length;
1489
1490 if ((A <= B + C) || (B <= C)) {
1491 return 0;
1492 }
1493
1494 return 1;
1495}
1496
1497typedef struct {
1498 size_t alloc;
1499 SORT_TYPE *storage;
1500} TEMP_STORAGE_T;
1501
1502static void TIM_SORT_RESIZE(TEMP_STORAGE_T *store, const size_t new_size) {
1503 if ((store->storage == NULL) || (store->alloc < new_size)) {
1504 SORT_TYPE *tempstore = (SORT_TYPE *)realloc(store->storage, new_size * sizeof(SORT_TYPE));
1505
1506 if (tempstore == NULL) {
1507 fprintf(stderr, "Error allocating temporary storage for tim sort: need %lu bytes",
1508 (unsigned long)(sizeof(SORT_TYPE) * new_size));
1509 exit(1);
1510 }
1511
1512 store->storage = tempstore;
1513 store->alloc = new_size;
1514 }
1515}
1516
1517static void TIM_SORT_MERGE(SORT_TYPE *dst, const TIM_SORT_RUN_T *stack, const int stack_curr,
1518 TEMP_STORAGE_T *store) {
1519 const size_t A = stack[stack_curr - 2].length;
1520 const size_t B = stack[stack_curr - 1].length;
1521 const size_t curr = stack[stack_curr - 2].start;
1522 SORT_TYPE *storage;
1523 size_t i, j, k;
1524 TIM_SORT_RESIZE(store, MIN(A, B));
1525 storage = store->storage;
1526
1527 /* left merge */
1528 if (A < B) {
1529 SORT_TYPE_CPY(storage, &dst[curr], A);
1530 i = 0;
1531 j = curr + A;
1532
1533 for (k = curr; k < curr + A + B; k++) {
1534 if ((i < A) && (j < curr + A + B)) {
1535 if (SORT_CMP(storage[i], dst[j]) <= 0) {
1536 dst[k] = storage[i++];
1537 } else {
1538 dst[k] = dst[j++];
1539 }
1540 } else if (i < A) {
1541 dst[k] = storage[i++];
1542 } else {
1543 break;
1544 }
1545 }
1546 } else {
1547 /* right merge */
1548 SORT_TYPE_CPY(storage, &dst[curr + A], B);
1549 i = B;
1550 j = curr + A;
1551 k = curr + A + B;
1552
1553 while (k-- > curr) {
1554 if ((i > 0) && (j > curr)) {
1555 if (SORT_CMP(dst[j - 1], storage[i - 1]) > 0) {
1556 dst[k] = dst[--j];
1557 } else {
1558 dst[k] = storage[--i];
1559 }
1560 } else if (i > 0) {
1561 dst[k] = storage[--i];
1562 } else {
1563 break;
1564 }
1565 }
1566 }
1567}
1568
1569static int TIM_SORT_COLLAPSE(SORT_TYPE *dst, TIM_SORT_RUN_T *stack, int stack_curr,
1570 TEMP_STORAGE_T *store, const size_t size) {
1571 while (1) {
1572 size_t A, B, C, D;
1573 int ABC, BCD, CD;
1574
1575 /* if the stack only has one thing on it, we are done with the collapse */
1576 if (stack_curr <= 1) {
1577 break;
1578 }
1579
1580 /* if this is the last merge, just do it */
1581 if ((stack_curr == 2) && (stack[0].length + stack[1].length == size)) {
1582 TIM_SORT_MERGE(dst, stack, stack_curr, store);
1583 stack[0].length += stack[1].length;
1584 stack_curr--;
1585 break;
1586 }
1587 /* check if the invariant is off for a stack of 2 elements */
1588 else if ((stack_curr == 2) && (stack[0].length <= stack[1].length)) {
1589 TIM_SORT_MERGE(dst, stack, stack_curr, store);
1590 stack[0].length += stack[1].length;
1591 stack_curr--;
1592 break;
1593 } else if (stack_curr == 2) {
1594 break;
1595 }
1596
1597 B = stack[stack_curr - 3].length;
1598 C = stack[stack_curr - 2].length;
1599 D = stack[stack_curr - 1].length;
1600
1601 if (stack_curr >= 4) {
1602 A = stack[stack_curr - 4].length;
1603 ABC = (A <= B + C);
1604 } else {
1605 ABC = 0;
1606 }
1607
1608 BCD = (B <= C + D) || ABC;
1609 CD = (C <= D);
1610
1611 /* Both invariants are good */
1612 if (!BCD && !CD) {
1613 break;
1614 }
1615
1616 /* left merge */
1617 if (BCD && !CD) {
1618 TIM_SORT_MERGE(dst, stack, stack_curr - 1, store);
1619 stack[stack_curr - 3].length += stack[stack_curr - 2].length;
1620 stack[stack_curr - 2] = stack[stack_curr - 1];
1621 stack_curr--;
1622 } else {
1623 /* right merge */
1624 TIM_SORT_MERGE(dst, stack, stack_curr, store);
1625 stack[stack_curr - 2].length += stack[stack_curr - 1].length;
1626 stack_curr--;
1627 }
1628 }
1629
1630 return stack_curr;
1631}
1632
1633static __inline int PUSH_NEXT(SORT_TYPE *dst,
1634 const size_t size,
1635 TEMP_STORAGE_T *store,
1636 const size_t minrun,
1637 TIM_SORT_RUN_T *run_stack,
1638 size_t *stack_curr,
1639 size_t *curr) {
1640 size_t len = COUNT_RUN(dst, *curr, size);
1641 size_t run = minrun;
1642
1643 if (run > size - *curr) {
1644 run = size - *curr;
1645 }
1646
1647 if (run > len) {
1648 BINARY_INSERTION_SORT_START(&dst[*curr], len, run);
1649 len = run;
1650 }
1651
1652 run_stack[*stack_curr].start = *curr;
1653 run_stack[*stack_curr].length = len;
1654 (*stack_curr)++;
1655 *curr += len;
1656
1657 if (*curr == size) {
1658 /* finish up */
1659 while (*stack_curr > 1) {
1660 TIM_SORT_MERGE(dst, run_stack, (int)*stack_curr, store);
1661 run_stack[*stack_curr - 2].length += run_stack[*stack_curr - 1].length;
1662 (*stack_curr)--;
1663 }
1664
1665 if (store->storage != NULL) {
1666 free(store->storage);
1667 store->storage = NULL;
1668 }
1669
1670 return 0;
1671 }
1672
1673 return 1;
1674}
1675
1676SORT_DEF void TIM_SORT(SORT_TYPE *dst, const size_t size) {
1677 size_t minrun;
1678 TEMP_STORAGE_T _store, *store;
1679 TIM_SORT_RUN_T run_stack[TIM_SORT_STACK_SIZE];
1680 size_t stack_curr = 0;
1681 size_t curr = 0;
1682
1683 /* don't bother sorting an array of size 1 */
1684 if (size <= 1) {
1685 return;
1686 }
1687
1688 if (size < 64) {
1689 SMALL_STABLE_SORT(dst, size);
1690 return;
1691 }
1692
1693 /* compute the minimum run length */
1694 minrun = compute_minrun(size);
1695 /* temporary storage for merges */
1696 store = &_store;
1697 store->alloc = 0;
1698 store->storage = NULL;
1699
1700 if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
1701 return;
1702 }
1703
1704 if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
1705 return;
1706 }
1707
1708 if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
1709 return;
1710 }
1711
1712 while (1) {
1713 if (!CHECK_INVARIANT(run_stack, (int)stack_curr)) {
1714 stack_curr = TIM_SORT_COLLAPSE(dst, run_stack, (int)stack_curr, store, size);
1715 continue;
1716 }
1717
1718 if (!PUSH_NEXT(dst, size, store, minrun, run_stack, &stack_curr, &curr)) {
1719 return;
1720 }
1721 }
1722}
1723
1724/* heap sort: based on wikipedia */
1725
1726static __inline void HEAP_SIFT_DOWN(SORT_TYPE *dst, const size_t start, const size_t end) {
1727 size_t root = start;
1728
1729 while ((root << 1) <= end) {
1730 size_t child = root << 1;
1731
1732 if ((child < end) && (SORT_CMP(dst[child], dst[child + 1]) < 0)) {
1733 child++;
1734 }
1735
1736 if (SORT_CMP(dst[root], dst[child]) < 0) {
1737 SORT_SWAP(dst[root], dst[child]);
1738 root = child;
1739 } else {
1740 return;
1741 }
1742 }
1743}
1744
1745static __inline void HEAPIFY(SORT_TYPE *dst, const size_t size) {
1746 size_t start = size >> 1;
1747
1748 while (1) {
1749 HEAP_SIFT_DOWN(dst, start, size - 1);
1750
1751 if (start == 0) {
1752 break;
1753 }
1754
1755 start--;
1756 }
1757}
1758
1759SORT_DEF void HEAP_SORT(SORT_TYPE *dst, const size_t size) {
1760 size_t end = size - 1;
1761
1762 /* don't bother sorting an array of size <= 1 */
1763 if (size <= 1) {
1764 return;
1765 }
1766
1767 HEAPIFY(dst, size);
1768
1769 while (end > 0) {
1770 SORT_SWAP(dst[end], dst[0]);
1771 HEAP_SIFT_DOWN(dst, 0, end - 1);
1772 end--;
1773 }
1774}
1775
1776#ifdef SORT_EXTRA
1777#include "sort_extra.h"
1778#endif
1779
1780#undef SORT_SAFE_CPY
1781#undef SORT_TYPE_CPY
1782#undef SORT_TYPE_MOVE
1783#undef SORT_NEW_BUFFER
1784#undef SORT_DELETE_BUFFER
1785#undef QUICK_SORT
1786#undef MEDIAN
1787#undef SORT_CONCAT
1788#undef SORT_MAKE_STR1
1789#undef SORT_MAKE_STR
1790#undef SORT_NAME
1791#undef SORT_TYPE
1792#undef SORT_CMP
1793#undef TEMP_STORAGE_T
1794#undef TIM_SORT_RUN_T
1795#undef PUSH_NEXT
1796#undef SORT_SWAP
1797#undef SORT_MAKE_STR1
1798#undef SORT_MAKE_STR
1799#undef BINARY_INSERTION_FIND
1800#undef BINARY_INSERTION_SORT_START
1801#undef BINARY_INSERTION_SORT
1802#undef REVERSE_ELEMENTS
1803#undef COUNT_RUN
1804#undef TIM_SORT
1805#undef TIM_SORT_RESIZE
1806#undef TIM_SORT_COLLAPSE
1807#undef TIM_SORT_RUN_T
1808#undef TEMP_STORAGE_T
1809#undef MERGE_SORT
1810#undef MERGE_SORT_RECURSIVE
1811#undef MERGE_SORT_IN_PLACE
1812#undef MERGE_SORT_IN_PLACE_RMERGE
1813#undef MERGE_SORT_IN_PLACE_BACKMERGE
1814#undef MERGE_SORT_IN_PLACE_FRONTMERGE
1815#undef MERGE_SORT_IN_PLACE_ASWAP
1816
1817#ifdef SORT_GCC_PUSH
1818#undef SORT_GCC_PUSH
1819#pragma GCC diagnostic pop
1820#endif
TIM_SORT_RESIZE
#define TIM_SORT_RESIZE
Definition sort.h:176
TIM_SORT
#define TIM_SORT
Definition sort.h:175
BINARY_INSERTION_SORT_START
#define BINARY_INSERTION_SORT_START
Definition sort.h:170
PUSH_NEXT
#define PUSH_NEXT
Definition sort.h:196
BITONIC_SORT_4
#define BITONIC_SORT_4
Definition sort.h:243
BITONIC_SORT_16
#define BITONIC_SORT_16
Definition sort.h:644
SMALL_SORT
#define SMALL_SORT
Definition sort.h:157
QUICK_SORT_RECURSIVE
#define QUICK_SORT_RECURSIVE
Definition sort.h:191
SORT_CSWAP
#define SORT_CSWAP(x, y)
Definition sort.h:205
SMALL_SORT_BND
#define SMALL_SORT_BND
Definition sort.h:154
TIM_SORT_COLLAPSE
#define TIM_SORT_COLLAPSE
Definition sort.h:178
MERGE_SORT_RECURSIVE
#define MERGE_SORT_RECURSIVE
Definition sort.h:183
SORT_TYPE_CPY
#define SORT_TYPE_CPY
Definition sort.h:164
CHECK_INVARIANT
#define CHECK_INVARIANT
Definition sort.h:174
MEDIAN
#define MEDIAN
Definition sort.h:180
SMALL_STABLE_SORT
#define SMALL_STABLE_SORT
Definition sort.h:161
BITONIC_SORT_3
#define BITONIC_SORT_3
Definition sort.h:235
TIM_SORT_MERGE
#define TIM_SORT_MERGE
Definition sort.h:177
BITONIC_SORT_15
#define BITONIC_SORT_15
Definition sort.h:583
BITONIC_SORT_10
#define BITONIC_SORT_10
Definition sort.h:359
COUNT_RUN
#define COUNT_RUN
Definition sort.h:173
SORT_TYPE_MOVE
#define SORT_TYPE_MOVE
Definition sort.h:165
MERGE_SORT_IN_PLACE
#define MERGE_SORT_IN_PLACE
Definition sort.h:184
MERGE_SORT_IN_PLACE_RMERGE
#define MERGE_SORT_IN_PLACE_RMERGE
Definition sort.h:185
QUICK_SORT_PARTITION
#define QUICK_SORT_PARTITION
Definition sort.h:190
SORT_NEW_BUFFER
#define SORT_NEW_BUFFER
Definition sort.h:166
MIN
#define MIN(x, y)
Definition sort.h:58
TEMP_STORAGE_T
#define TEMP_STORAGE_T
Definition sort.h:195
REVERSE_ELEMENTS
#define REVERSE_ELEMENTS
Definition sort.h:172
HEAP_SIFT_DOWN
#define HEAP_SIFT_DOWN
Definition sort.h:192
MERGE_SORT
#define MERGE_SORT
Definition sort.h:182
SHELL_SORT
#define SHELL_SORT
Definition sort.h:189
TIM_SORT_STACK_SIZE
#define TIM_SORT_STACK_SIZE
Definition sort.h:42
BITONIC_SORT_7
#define BITONIC_SORT_7
Definition sort.h:284
BITONIC_SORT
#define BITONIC_SORT
Definition sort.h:168
SORT_DELETE_BUFFER
#define SORT_DELETE_BUFFER
Definition sort.h:167
BITONIC_SORT_9
#define BITONIC_SORT_9
Definition sort.h:329
SORT_SWAP
#define SORT_SWAP(x, y)
Definition sort.h:46
QUICK_SORT
#define QUICK_SORT
Definition sort.h:181
MAX
#define MAX(x, y)
Definition sort.h:54
HEAPIFY
#define HEAPIFY
Definition sort.h:193
SORT_CMP
#define SORT_CMP(x, y)
Definition sort.h:19
BINARY_INSERTION_SORT
#define BINARY_INSERTION_SORT
Definition sort.h:171
BITONIC_SORT_13
#define BITONIC_SORT_13
Definition sort.h:477
BITONIC_SORT_5
#define BITONIC_SORT_5
Definition sort.h:253
CLZ
#define CLZ
Definition sort.h:119
TIM_SORT_RUN_T
#define TIM_SORT_RUN_T
Definition sort.h:194
BITONIC_SORT_11
#define BITONIC_SORT_11
Definition sort.h:393
BITONIC_SORT_12
#define BITONIC_SORT_12
Definition sort.h:433
MERGE_SORT_IN_PLACE_BACKMERGE
#define MERGE_SORT_IN_PLACE_BACKMERGE
Definition sort.h:186
BITONIC_SORT_2
#define BITONIC_SORT_2
Definition sort.h:229
MERGE_SORT_IN_PLACE_ASWAP
#define MERGE_SORT_IN_PLACE_ASWAP
Definition sort.h:188
MERGE_SORT_IN_PLACE_FRONTMERGE
#define MERGE_SORT_IN_PLACE_FRONTMERGE
Definition sort.h:187
HEAP_SORT
#define HEAP_SORT
Definition sort.h:179
BINARY_INSERTION_FIND
#define BINARY_INSERTION_FIND
Definition sort.h:169
BITONIC_SORT_8
#define BITONIC_SORT_8
Definition sort.h:305
BITONIC_SORT_6
#define BITONIC_SORT_6
Definition sort.h:267
BITONIC_SORT_14
#define BITONIC_SORT_14
Definition sort.h:527
TEMP_STORAGE_T::alloc
size_t alloc
Definition sort.h:1498
TEMP_STORAGE_T::storage
SORT_TYPE * storage
Definition sort.h:1499
TIM_SORT_RUN_T::start
size_t start
Definition sort.h:209
TIM_SORT_RUN_T::length
size_t length
Definition sort.h:210
p
params_t *const p
Definition util_io.c:93
SORT_DEF
#define SORT_DEF
Definition util_m4ri.c:568
SORT_TYPE
#define SORT_TYPE
Definition util_m4ri.c:566
Generated by doxygen 1.15.0