How to implement classic sorting algorithms in modern C++?

Algorithmic building blocks

We begin by assembling the algorithmic building blocks from the Standard Library:

#include <algorithm>    // min_element, iter_swap, 
                        // upper_bound, rotate, 
                        // nth_element, partition, 
                        // inplace_merge,
                        // make_heap, sort_heap, push_heap, pop_heap,
                        // is_heap, is_sorted
#include <cassert>      // assert 
#include <functional>   // less
#include <iterator>     // iterator_traits, distance, next

Note that C++11 adds the xxx_heap related algorithms. Another useful C++11 utility is to define a template alias to extract an iterator's value type:

template<class It>
using value_type_t = typename std::iterator_traits<It>::value_type;

This can be used in combination with C++11's default function template arguments to create a single wrapper for sorting algorithms that take < as comparison and those that have a user-defined comparison function object.

Notes:

• I use Herb Sutter's almost always auto recommendation, for which the brevity is unsurpassed, although its clarity is sometimes disputed.
• I use a for (auto it = first; it != last; ++it) pattern in some places, in order to allow for loop invariant checking for already sorted sub-ranges. In production code, it is probably better to use while (first != last) and a ++first somewhere inside the loop.

Selection sort

Selection sort does not adapt to the data in any way, so its runtime is always O(N^2). However, selection sort has the property of minimizing the number of swaps. In applications where the cost of swapping items is high, selection sort very well may be the algorithm of choice.

To implement it using the Standard Library, repeatedly use std::min_element to find the remaining minimum element, and iter_swap to swap it into place:

template<class FwdIt, class Compare = std::less<value_type_t<FwdIt>>>
void selection_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last; ++it) {
        auto const selection = std::min_element(it, last, cmp);
        std::iter_swap(selection, it); 
        assert(std::is_sorted(first, std::next(it), cmp));
    }
}

Note that selection_sort has the already processed range [first, it) sorted as its loop invariant. The minimal requirements are forward iterators, compared to std::sort's random access iterators.

Insertion sort

Although it is one of the elementary sorting algorithms with O(N^2) worst-case time, insertion sort is the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has low overhead). For these reasons, and because it is also stable, insertion sort is often used as the recursive base case (when the problem size is small) for higher overhead divide-and-conquer sorting algorithms, such as merge sort or quick sort.

To implement insertion_sort with the Standard Library, repeatedly use std::upper_bound to find the location where the current element needs to go, and use std::rotate to shift the remaining elements upward in the input range:

template<class FwdIt, class Compare = std::less<value_type_t<FwdIt>>>
void insertion_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last; ++it) {
        auto const insertion = std::upper_bound(first, it, *it, cmp);
        std::rotate(insertion, it, std::next(it)); 
        assert(std::is_sorted(first, std::next(it), cmp));
    }
}

Note that insertion_sort has the already processed range [first, it) sorted as its loop invariant. Insertion sort also works with forward iterators.

Quick sort

When carefully implemented, quick sort is robust and has low overhead. When a stable sort is not needed, quick sort is an excellent general-purpose sort.

The simplest version of quick_sort is straightforward to implement using the Standard Library: use a few iterator utilities to locate the middle of the input range [first, last) as the pivot, use std::nth_element to separate the input range into element that are either smaller or equal to or larger than the selected pivot. Finally the two segments are recursively sorted:

template<class FwdIt, class Compare = std::less<value_type_t<FwdIt>>>
void quick_sort(FwdIt first, FwdIt last, Compare cmp = Compare{})
{
    auto const N = std::distance(first, last);
    if (N <= 1) return;
    auto const pivot = std::next(first, N / 2);
    std::nth_element(first, pivot, last, cmp);
    quick_sort(first, pivot, cmp); // assert(std::is_sorted(first, pivot, cmp));
    quick_sort(pivot, last, cmp);  // assert(std::is_sorted(pivot, last, cmp));
}

Note that although quick sort in general works with forward iterators, the above implementation cheats on this promise by using std::nth_element, which requires random access iterators (it can be remedied by choosing the pivot differently, see below).

However, quick sort is rather tricky to get correct and efficient, as each of the above steps has to be carefully checked and optimized for production level code.

Details omitted:

• median-of-3 pivot selection from randomly chosen elements from the input range in combination with std::partition to segment the input range around the pivot.
• This guards against almost sorted inputs for which the complexity would otherwise deteriorate to O(N^2) and would also weaken the requirements to the advertised forward iterators (since C++11, before that it was bidirectional iterators) instead of random access iterators that are imposed by std::nth_element.
• 3-way partitioning (separating elements smaller than, equal to and larger than the pivot) version should be used instead of the 2-way partitioning code (keeping elements equal to and larger than the pivot together). The latter exhibits poor locality, and, critically, exhibits O(N^2) time when there are few unique keys.

Merge sort

If using O(N) extra space is of no concern, then merge sort is an excellent choice: it is the only stable O(N log N) sorting algorithm.

It is simple to implement using Standard algorithms: use a few iterator utilities to locate the middle of the input range [first, last) and combine two recursively sorted segments with a std::inplace_merge:

template<class BiDirIt, class Compare = std::less<value_type_t<BiDirIt>>>
void merge_sort(BiDirIt first, BiDirIt last, Compare cmp = Compare{})
{
    auto const N = std::distance(first, last);
    if (N <= 1) return;                   
    auto const middle = std::next(first, N / 2);
    merge_sort(first, middle, cmp); // assert(std::is_sorted(first, middle, cmp));
    merge_sort(middle, last, cmp);  // assert(std::is_sorted(middle, last, cmp));
    std::inplace_merge(first, middle, last, cmp); // assert(std::is_sorted(first, last, cmp));
}

Merge sort requires bidirectional iterators, the bottleneck being the std::inplace_merge. Note that when sorting linked lists, merge sort requires only O(log N) extra space (for recursion). The latter algorithm is implemented by std::list<T>::sort in the Standard Library.

Heap sort

Heap sort is simple to implement, performs an O(N log N) in-place sort, but is not stable.

The first loop, O(N) "heapify" phase, puts the array into heap order. The second loop, the O(N log N) "sortdown" phase, repeatedly extracts the maximum and restores heap order. The Standard Library makes this extremely straightforward:

template<class RandomIt, class Compare = std::less<value_type_t<RandomIt>>>
void heap_sort(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    std::make_heap(first, last, cmp); // assert(std::is_heap(first, last, cmp));
    std::sort_heap(first, last, cmp); // assert(std::is_sorted(first, last, cmp));
}

In case you consider it "cheating" to use std::make_heap and std::sort_heap, you can go one level deeper and write those functions yourself in terms of std::push_heap and std::pop_heap, respectively:

namespace lib {

// NOTE: is O(N log N), not O(N) as std::make_heap
template<class RandomIt, class Compare = std::less<value_type_t<RandomIt>>>
void make_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    for (auto it = first; it != last;) {
        std::push_heap(first, ++it, cmp); 
        assert(std::is_heap(first, it, cmp));           
    }
}

template<class RandomIt, class Compare = std::less<value_type_t<RandomIt>>>
void sort_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    for (auto it = last; it != first;) {
        std::pop_heap(first, it--, cmp);
        assert(std::is_heap(first, it, cmp));           
    } 
}

}   // namespace lib

The Standard Library specifies both push_heap and pop_heap as complexity O(log N). Note however that the outer loop over the range [first, last) results in O(N log N) complexity for make_heap, whereas std::make_heap has only O(N) complexity. For the overall O(N log N) complexity of heap_sort it doesn't matter.

Details omitted: O(N) implementation of make_heap

Testing

Here is a Live Example testing all five algorithms on a variety of inputs (not meant to be exhaustive or rigorous).

As an addition to TRex make_heap, here is an implementation of push_heap, feel free to edit this into previous answer if you find it helpful.

/**
 * Pre: heap is [first, last -2.]
 * Arrange element last - 1 into heap. *parent >= *child.
 */
template<class RandomIt, class Compare = std::less<value_type_t<RandomIt>>>
void push_heap(RandomIt first, RandomIt last, Compare cmp = Compare{})
{
    auto child = last -1;
    auto parent_index = [=](RandomIt child) { 
        return ( std::distance( first, child ) -1 ) / 2; };
    auto parent = first + parent_index(child);

    while( std::max(*parent, *child, cmp ) != *parent ){
        std::iter_swap( parent, child );
        child = parent;
        parent = std::next( first, parent_index(child) );
    }
}

Any suggestions are welcome.