1 module nxt.hybridsort;
2 
3 import nxt.bijections : IntegralBijectableTypes;
4 
5 static immutable size_t[IntegralBijectableTypes.length] radixSortMinLength;
6 
7 shared static this()
8 {
9     foreach (i, E; IntegralBijectableTypes)
10     {
11         // TODO: Calculate radixSortMinLength for E
12         radixSortMinLength[i] = 0; // calulate limit
13     }
14 }
15 
16 import std.range.primitives : isRandomAccessRange;
17 
18 /** Perform either radix or standard sort depending on `ElementType` of `Range`.
19  */
20 auto hybridSort(alias less = "a < b", Range)(Range r)
21 if (isRandomAccessRange!Range)
22 {
23     import std.range.primitives : ElementType;
24     import std.traits : isNumeric;
25     static if (isNumeric!(ElementType!Range))
26     {
27         import nxt.integer_sorting : radixSort;
28         return radixSort(r);
29     }
30     else
31     {
32         import std.algorithm.sorting : sort;
33         return sort!less(r);
34     }
35 }
36 
37 ///
38 unittest
39 {
40     import std.meta : AliasSeq;
41     const n = 10_000;
42     foreach (ix, T; AliasSeq!(byte, short))
43     {
44         import std.container : Array;
45         import std.algorithm : isSorted, swap;
46         import nxt.random_ex : randInPlace;
47 
48         auto a = Array!T();
49         a.length = n;
50 
51         randInPlace(a[]);
52 
53         auto b = a.dup;
54 
55         hybridSort(a[]);
56         assert(a[].isSorted);
57 
58         import std.algorithm.sorting : sort;
59         sort(b[]);
60         assert(b[].isSorted);
61 
62         assert(a == b);
63 
64         swap(a, b);
65     }
66 }