C++ Compile-Time Quick Sort

There used to be an internet joke about someone proficient in C++ who, after going to an interview, received a market education. One of the questions was to implement a compile-time sort in C++. This blog post will tackle that challenge.

Algorithm

Quick sort, unlike many other sorting algorithms, is well expressed mathematically, as evidenced by its Haskell implementation.

quicksort [] = []
quicksort (x:xs) = 
     quicksort [y | y <- xs, y <= x] ++ [x] ++ quicksort [y | y <- xs, y > x]

The idea is to take the first element, partition the remaining elements into those less than and those greater than this element, recursively apply quicksort to these partitions, and finally merge them.

C++ template metaprogramming is fundamentally functional programming, so implementing quicksort at compile-time in C++ is relatively simple compared to other sorting algorithms. (Although, it is still challenging.)

Implementation

List and Its Algorithms

First, let’s define a list, which is straightforward. For simplicity, all data types here use int​. It is not difficult to extend this with a data type template parameter once you understand the entire blog.

template <int ... N>
struct NumberList;

Next is getting the first element of a list:

// Get Front Element
template <typename List>
struct FrontElementT;

template <int Head, int ... Tail>
struct FrontElementT<NumberList<Head, Tail...>> {
    static const int value = Head;
};
template <typename List>
static const int FrontElement = FrontElementT<List>::value;

Note that we do not handle the case of an empty list here, so it will directly cause a compilation error if the list is empty.

Then, we fetch the remaining elements of a list after removing the first element, PopFront​:

// Pop Front
template <typename List>
struct PopFrontT;

template <int Head, int ... Tail>
struct PopFrontT<NumberList<Head, Tail...>> {
    using type = NumberList<Tail...>;
};
template <typename List>
using PopFront = typename PopFrontT<List>::type;

Again, we do not handle the case of an empty list, mainly because it is unnecessary.

For quicksort, the most crucial part is Partition​. We might think we need to keep adding elements to a list continually, so we implement PushFront​ to add an element to the front of the list:

// Push Front
template <int Element, typename List>
struct PushFrontT;

template <int Element, int ... N>
struct PushFrontT<Element, NumberList<N...>> {
    using type = NumberList<Element, N...>;
};
template <int Element, typename List>
using PushFront = typename PushFrontT<Element, List>::type;

Note: You could also implement a PushBack​ similarly by modifying the order of N…​ and Element​ in the NumberList above. However, since this quicksort implementation does not use PushBack​, it is omitted.

Partition

With list addition and removal implemented, the next key step in quicksort is Partition. The idea here is to split a list into two parts compared to a pivot element. One part contains elements smaller than the pivot, and the other part contains elements larger than or equal to the pivot.

Generally, we might prefer to abstract out this comparison operation, so we first create an ordering relation:

template<int L, int R>
struct Less {
    static constexpr bool value = L < R;
};

Next, we implement PartitionLeft​ to get the sublist that satisfies the ordering relation (i.e., elements smaller than the pivot):

// Partition Left
template <int Pivot, typename List, template <int, int> typename Compare>
struct PartitionLeftT;

template <int Pivot, int Head, int ... Tail, template<int, int> typename Compare>
struct PartitionLeftT<Pivot, NumberList<Head, Tail...>, Compare> {
    using type = typename std::conditional_t<Compare<Head, Pivot>::value,
                                             PushFront<Head, typename PartitionLeftT<Pivot, NumberList<Tail...>, Compare>::type>,
                                             typename PartitionLeftT<Pivot, NumberList<Tail...>, Compare>::type>;
};
template <int Pivot, template<int, int> typename Compare>
struct PartitionLeftT<Pivot, NumberList<>, Compare> {
    using type = NumberList<>;
};
template <int Pivot, typename List, template<int, int> typename Compare>
using PartitionLeft = typename PartitionLeftT<Pivot, List, Compare>::type;

The crucial part is the std::conditional_t​ segment. When the ordering condition is met, we perform PushFront​. Note that it must be PushFront​ and not PushBack​ because this is a recursion, and the new list is generated by first adding the latter elements and then the previous ones.

Once you understand PartitionLeft​, implementing PartitionRight​ is straightforward, just change the comparison operator.

// Partition Right
template <int Pivot, typename List, template<int, int> typename Compare>
struct PartitionRightT;

template <int Pivot, int Head, int ... Tail, template<int, int> typename Compare>
struct PartitionRightT<Pivot, NumberList<Head, Tail...>, Compare> {
    using type = typename std::conditional_t<!Compare<Head, Pivot>::value,
                                             PushFront<Head, typename PartitionRightT<Pivot, NumberList<Tail...>, Compare>::type>,
                                             typename PartitionRightT<Pivot, NumberList<Tail...>, Compare>::type>;
};
template <int Pivot, template<int, int> typename Compare>
struct PartitionRightT<Pivot, NumberList<>, Compare> {
    using type = NumberList<>;
};
template <int Pivot, typename List, template<int, int> typename Compare>
using PartitionRight = typename PartitionRightT<Pivot, List, Compare>::type;

Following the quick sort algorithm, the next step is to recursively call quicksort on the two partitions and then merge them. Here is the merge code, which is straightforward:

// Concatenate
template <typename LList, int M, typename RList>
struct ConcatenateT;

template <int ... L, int M, int ... R>
struct ConcatenateT<NumberList<L...>, M, NumberList<R...>> {
    using type = NumberList<L..., M, R...>;
};
template <typename LList, int M, typename RList>
using Concatenate = typename ConcatenateT<LList, M, RList>::type;

Quick Sort

Lastly, here is the quicksort section. The core code is as follows:

// Quick sort
template <typename List, template<int, int> typename Compare>
struct QuickSortT {
  using Result = Concatenate<typename QuickSortT<PartitionLeft<FrontElement<List>, PopFront<List>, Compare>, Compare>::Result,
                             FrontElement<List>,
                             typename QuickSortT<PartitionRight<FrontElement<List>, PopFront<List>, Compare>, Compare>::Result>;
};

Invoke quicksort on PartitionLeft​ and PartitionRight​, and then merge them.

Finally, handle the recursion base cases and perform the final type aliasing.

template <template<int, int> typename Compare>
struct QuickSortT<NumberList<>, Compare> {
  using Result = NumberList<>;
};

template <int N, template<int, int> typename Compare>
struct QuickSortT<NumberList<N>, Compare> {
  using Result = NumberList<N>;
};
template <typename List, template<int, int> typename Compare>
using QuickSort = typename QuickSortT<List, Compare>::Result;

With this, the entire compile-time quicksort is complete.