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);
			}
		}
	}
}