module nxt.hybridsort;

import nxt.bijections : IntegralBijectableTypes;

static immutable size_t[IntegralBijectableTypes.length] radixSortMinLength;

shared static this()
{
    foreach (i, E; IntegralBijectableTypes)
    {
        // TODO Calculate radixSortMinLength for E
        radixSortMinLength[i] = 0; // calulate limit
    }
}

import std.range.primitives : isRandomAccessRange;

/** Perform either radix or standard sort depending on `ElementType` of `Range`.
 */
auto hybridSort(alias less = "a < b", Range)(Range r)
if (isRandomAccessRange!Range)
{
    import std.range.primitives : ElementType;
    import std.traits : isNumeric;
    static if (isNumeric!(ElementType!Range))
    {
        import nxt.integer_sorting : radixSort;
        return radixSort(r);
    }
    else
    {
        import std.algorithm.sorting : sort;
        return sort!less(r);
    }
}

unittest
{
    import std.meta : AliasSeq;

    const n = 1_000_000;

    foreach (ix, T; AliasSeq!(byte, short))
    {
        import std.container : Array;
        import std.algorithm : isSorted, swap;
        import nxt.random_ex : randInPlace;

        auto a = Array!T();
        a.length = n;

        randInPlace(a[]);

        auto b = a.dup;

        hybridSort(a[]);
        assert(a[].isSorted);

        import std.algorithm.sorting : sort;
        sort(b[]);
        assert(b[].isSorted);

        assert(a == b);

        swap(a, b);
    }
}