Alternative make_poplar implementation

make_poplar.hpp

template<typename RandomAccessIterator, typename Compare, typename Projection>
auto make_poplar(RandomAccessIterator first, RandomAccessIterator last,
                 Compare compare, Projection projection)
    -> void
{
    auto size = std::distance(first, last);
    if (size < 16) {
        // A sorted collection is a valid poplar heap;
        // when the heap is small, using insertion sort
        // should be faster
        insertion_sort(std::move(first), std::move(last),
                       std::move(compare), std::move(projection));
        return;
    }

    using poplar_level_t = std::make_unsigned_t<difference_type_t<RandomAccessIterator>>;
    poplar_level_t poplar_level = 1;

    auto it = first;
    auto next = std::next(it, 15);
    while (true) {
        // Make a 15 element poplar
        unchecked_insertion_sort(it, next, compare, projection);

        // Sift elements to collapse poplars
        auto poplar_size = 15;
        auto begin = it;
        // The loop increment follows the binary carry sequence for some reason
        for (auto i = (poplar_level & -poplar_level) >> 1 ; i != 0 ; i >>= 1) {
            begin -= poplar_size;
            poplar_size = 2 * poplar_size + 1;
            sift(begin, poplar_size, compare, projection);
            ++next;
        }

        if (next == last) return;
        it = next;
        std::advance(next, 15);
        ++poplar_level;
    }
}