Tentative improvement over probe::dis

dis-new.h++

template<typename BidirectionalIterator, typename Compare, typename Projection>
auto allocating_dis_probe_algo(BidirectionalIterator first, BidirectionalIterator last,
                               cppsort::detail::difference_type_t<BidirectionalIterator> size,
                               Compare compare, Projection projection)
    -> ::cppsort::detail::difference_type_t<BidirectionalIterator>
{
    using difference_type = ::cppsort::detail::difference_type_t<BidirectionalIterator>;
    auto&& comp = utility::as_function(compare);
    auto&& proj = utility::as_function(projection);

    // Space-optimized version of the algorithm described in *Roughly Sorting:
    // Sequential and Parallel Approach* by T. Altman and Y. Igarashi

    if (size < 2) {
        return 0;
    }

    // Algorithm LR: cumulative max from left to right
    cppsort::detail::immovable_vector<BidirectionalIterator> lr_cummax(size);
    lr_cummax.emplace_back(first);
    for (auto it = std::next(first) ; it != last ; ++it) {
        if (comp(proj(*lr_cummax.back()), proj(*it))) {
            lr_cummax.emplace_back(it);
        } else {
            lr_cummax.emplace_back(lr_cummax.back());
        }
    }

    // Merged algorithms without extra storage:
    // - RL: cumulative min from right to left
    // - DM: max distance of an inversion
    difference_type res = 0;
    difference_type i = size;
    auto rl_it = std::prev(last); // Iterator to the current RL element
    auto rl_min_it = rl_it; // Iterator to the current minimum of RL
    for (auto j = i ; j > 0 ; --j) {
        while (j > 0 && comp(proj(*rl_min_it), proj(*lr_cummax[j - 1]))) {
            --j;
        }
        res = std::max(res, i - j - 1);
        do {
            if (--i <= res) {
                return res;
            }
            --rl_it;
            if (comp(proj(*rl_it), proj(*rl_min_it))) {
                rl_min_it = rl_it;
            }
        } while (i > j && not comp(proj(*rl_min_it), proj(*lr_cummax[j - 1])));
    }

    return res;
}