mergesort.cpp

template <typename, typename> struct is_less_than;
template <int X, int Y> struct is_less_than<Int<X>, Int<Y>> : std::bool_constant<(X < Y)> {};
template <typename A, typename B> static constexpr bool is_less_than_v = is_less_than<A, B>::value;

template <typename, typename, typename=void> struct do_merge;
template <typename As, typename Bs> using merge = typename do_merge<As, Bs>::type;

// Need this because specialisations are chosen by specificity and
// ties are broken not by order but by compiler error.
template <>
struct do_merge<tuple<>, tuple<>> {
	using type = tuple<>;
};
template <typename... Ts>
struct do_merge<tuple<Ts...>, tuple<>> {
	using type = tuple<Ts...>;
};
template <typename... Ts>
struct do_merge<tuple<>, tuple<Ts...>> {
	using type = tuple<Ts...>;
};
template <typename A, typename B, typename... As, typename... Bs>
struct do_merge<tuple<A, As...>, tuple<B, Bs...>, enable_if_t<is_less_than_v<A, B>>> {
	using type = concat<tuple<A>, typename do_merge<tuple<As...>, tuple<B, Bs...>>::type>;
};
template <typename A, typename B, typename... As, typename... Bs>
struct do_merge<tuple<A, As...>, tuple<B, Bs...>, enable_if_t<!is_less_than_v<A, B>>> {
	using type = concat<tuple<B>, typename do_merge<tuple<A, As...>, tuple<Bs...>>::type>;
};

static_assert(is_same_v<merge<tuple<>, tuple<>>, tuple<>>);
static_assert(is_same_v<merge<tuple<Int<0>>, tuple<>>, tuple<Int<0>>>);
static_assert(is_same_v<merge<tuple<Int<0>>, tuple<Int<1>>>, tuple<Int<0>, Int<1>>>);
static_assert(is_same_v<merge<tuple<Int<1>>, tuple<Int<0>>>, tuple<Int<0>, Int<1>>>);

template <typename> struct do_mergesort;
template <typename L> using mergesort = typename do_mergesort<L>::type;

template <>
struct do_mergesort<tuple<>> {
	using type = tuple<>;
};
template <typename T>
struct do_mergesort<tuple<T>> {
	using type = tuple<T>;
};
template <typename... Ts>
struct do_mergesort<tuple<Ts...>> {
	static constexpr int N = sizeof...(Ts) / 2;
	using type = merge<
		mergesort<take<N, tuple<Ts...>>>, 
		mergesort<drop<N, tuple<Ts...>>>
	>;
};

static_assert(is_same_v<mergesort<tuple<>>, tuple<>>);
static_assert(is_same_v<mergesort<tuple<Int<1>>>, tuple<Int<1>>>);
static_assert(is_same_v<mergesort<tuple<Int<1>, Int<2>>>, tuple<Int<1>, Int<2>>>);
static_assert(is_same_v<mergesort<tuple<Int<2>, Int<1>>>, tuple<Int<1>, Int<2>>>);
static_assert(is_same_v<mergesort<tuple<Int<1>, Int<2>, Int<3>>>, tuple<Int<1>, Int<2>, Int<3>>>);
static_assert(is_same_v<mergesort<tuple<Int<1>, Int<3>, Int<2>>>, tuple<Int<1>, Int<2>, Int<3>>>);
static_assert(is_same_v<mergesort<tuple<Int<2>, Int<1>, Int<3>>>, tuple<Int<1>, Int<2>, Int<3>>>);
static_assert(is_same_v<mergesort<tuple<Int<2>, Int<3>, Int<1>>>, tuple<Int<1>, Int<2>, Int<3>>>);
static_assert(is_same_v<mergesort<tuple<Int<3>, Int<1>, Int<2>>>, tuple<Int<1>, Int<2>, Int<3>>>);
static_assert(is_same_v<mergesort<tuple<Int<3>, Int<2>, Int<1>>>, tuple<Int<1>, Int<2>, Int<3>>>);