Simple in-place splitsort implementation

split_sort.hpp

#include <algorithm>
#include <iterator>

template<typename Iterator, typename Compare>
void split_sort(Iterator first, Iterator last, Compare compare)
{
    if (std::distance(first, last) < 2) return;

    // Read and reorganize elements until middle is found
    auto middle = first; // Last element of the LAS
    for (auto reader_it = std::next(first) ; reader_it != last ; ++reader_it) {
        if (compare(*reader_it, *middle)) {
            // We remove the top of the subsequence as well as the new element
            if (middle != first) {
                --middle;
            }
        } else {
            // Everything is fine, add the new element to the subsequence
            ++middle;
            if (middle != reader_it) {
                iter_swap(middle, reader_it);
            }
        }
    }

    // Sort second part of the collection and merge
    std::sort(middle, last, compare);
    std::inplace_merge(first, middle, last, compare);
}