Sorting algorithm based on the longest descending subsequence

lds_sort.hpp

#include <iterator>
#include <cpp-sort/detail/inplace_merge.h>
#include <cpp-sort/detail/lower_bound.h>
#include <cpp-sort/sorters/pdq_sorter.h>
#include <cpp-sort/utility/as_function.h>
#include <cpp-sort/utility/iter_move.h>

template<typename RandomAccessIterator, typename Compare, typename Projection>
auto lds_sort(RandomAccessIterator first, RandomAccessIterator last,
              Compare compare, Projection projection)
    -> void
{
    using utility::iter_swap;

    auto size = std::distance(first, last);
    if (size < 2) return;

    auto&& proj = utility::as_function(projection);

    RandomAccessIterator lds_begin = last;
    RandomAccessIterator cursor = first;

    while (cursor != lds_begin) {
        auto it = cppsort::detail::lower_bound(
            lds_begin, last, proj(*cursor),
            compare, projection);

        if (it == last) {
            if (lds_begin == last) {
                --lds_begin;
                iter_swap(lds_begin, cursor);
            } else {
                iter_swap(std::prev(last), cursor);
            }
        }
        else if (it == lds_begin) {
            --lds_begin;
            if (lds_begin == cursor) {
                ++lds_begin;
                break;
            }
            iter_swap(lds_begin, cursor);
        } else {
            iter_swap(it, cursor);
        }
        ++cursor;
    }

    pdq_sort(first, lds_begin, compare, projection);
    detail::inplace_merge(first, lds_begin, last, compare, projection);
}