## Post contents

So I've written about compile time quick sort twice before (2011 and 2015,) but now when C++17 support is becoming available, I thought I'd try it again.

I'll be taking advantage
of `std::integral_constant<type, value>`

a lot. It has the
advantage that it encodes the value in the type directly, while still allowing arithmetics as if it was a constant of
the type. Unfortunately, it's rather much to write, so to save typing, a
convenient variable template is introduced:

`template <auto N>std::integral_constant<decltype(N), N> c;`

This brings a convenient short hand notation `c<3U>`

meaning an lvalue of
type `std::integral_constant<unsigned int, 3U>`

.
Line 1 shows `template <auto>`

, which is a very handy new feature in C++17 for non-type template parameters, where the
type is deduced. You can see example usage in the Compiler Explorer(
thanks @mattgodbolt.)

Before we can go on to sorting, we need a way to express a range to sort, and to operate on those ranges. I've used a
simple `type_list`

template:

`template <typename ... T>struct type_list{ constexpr type_list(T...) {}};`

The constructor is there to take advantage of another new C++17
feature: automatic template parameter deduction.
It's possible to write `type_list{c<3>, c<8>}`

to construct an instance of `type_list<std::integral_constant<int, 3>, std::integral_constant<int, 8>>`

. Here, (line 4 above) the actual values aren't used in the `type_list`

, it's the types
alone that are interesting. The values are just used to guide the compiler to deduce the types correctly. The same
technique can be used in more conventional programming, for example `std::pair{3, 'c'}`

constructs
a `std::pair<int, char>`

which holds the values `3`

and `'c'`

.

Now we need a few functions to operate on the type lists:

`template <typename T, typename ... Ts>constexpr auto head(type_list<T, Ts...>){ return T{};}template <typename T, typename ... Ts>constexpr auto tail(type_list<T, Ts...>){ return type_list{Ts{}...};}template <typename ... Ts, typename ... Us>constexpr auto operator|(type_list<Ts...>, type_list<Us...>){ return type_list{Ts{}..., Us{}...};}`

Both `tail()`

and the concatenating `operator|()`

use
the automatic template parameter deductionto
construct the returned `type_list`

. Here's a compiler explorer to play around a bit with
them.

Now comes the matter of partitioning a `type_list`

into two lists based on comparison with a pivot element. The easiest
way to do this is a classic recursion:

`template <typename Compare, typename P, typename ... Ts>constexpr auto partition(Compare compare, P pivot, type_list<Ts...> tl){ if constexpr (sizeof...(Ts) == 0) { return std::pair(type_list{}, type_list{}); } else { constexpr auto h = head(tl); constexpr auto r = partition(compare, pivot, tail(tl)); if constexpr (compare(h, pivot)) { return std::pair(type_list{h} | r.first, r.second); } else { return std::pair(r.first, type_list{h} | r.second); } }}`

`if constexpr`

is a new C++17 construction (often referred to
as
constexpr-if,) that is a major blessing when doing template programming. Unlike an ordinary `if`

statement, `if constexpr`

only generates code for the branch selected by the `constexpr`

condition.

Above, the `else`

branch doesn't compile for an empty `type_list<> tl`

, so an ordinary `if`

statement would give a
compilation error. In C++14 and earlier, it would be necessary to write two separate `partition`

functions, one that
matches the empty list, and one for the general case.

So, given a compare function, a pivot value, and a `type_list<Ts...>`

, the function `partition`

returns a pair of type
lists. The first containing the Ts that are true for `compare(pivot, t)`

, and the second containing the other Ts. The
compare function can be an ordinary lambda. In C++17, lambdas are `constexpr`

(when possible.)

Checkout this Compiler Explorer to play with it.

Now all bits necessary for doing quick sort are in place, and it's an almost embarrassingly simple textbook-style recursive solution:

`template <typename Compare, typename ... T>constexpr auto sort(type_list<T...> tl, Compare compare){ if constexpr (sizeof...(T) == 0) { return type_list{}; } else { constexpr auto pivot = head(tl); constexpr auto r = partition(compare, pivot, tail(tl)); return sort(r.first, compare) | type_list{pivot} | sort(r.second, compare); }}`

Here's a compiler explorer that converts the sorted `type_list<>`

into a `std::array<>,`

just to visualise the data generated. You may notice that the optimisation level chosen is **-O0**, and yet no code is
generated to produce the sorted array.

As before, the usefulness of this is very limited, but it is kind of cool, isn't it?