hybridSort

import std.algorithm.sorting : isSorted;
import std.algorithm.iteration : permutations;
import std.range : iota;
import std.random : randomShuffle, Random;

Random random;

alias T = uint;

const maxFullPermutationTestLength = 8;
const maxTriedShufflings = 10_000; // maximum number of shufflings to try

import std.meta : AliasSeq;
foreach (less; AliasSeq!("a < b", "a > b"))
{
    foreach (const n; 0 .. networkSortMaxLength + 1)
    {
        if (n > maxFullPermutationTestLength) // if number of elements is too large
        {
            foreach (x; 0 .. maxTriedShufflings)
            {
                import std.array : array;
                auto y = iota(0, n).array;
                y.randomShuffle(random);
                y.hybridSort!less;
                assert(y.isSorted!less);
            }
        }
        else
        {
            foreach (x; iota(0, n).permutations)
            {
                import std.array : array;
                auto y = x.array;
                y.hybridSort!less;
                assert(y.isSorted!less);
            }
        }
    }
}