Return to Answer

e: Unfortunately, this solution only works if you had a real bit_vector container (not std::vector<bool>) that specialized the various <algorithm> functions like std::find().

template <typename ForwardIterator, typename T>
auto find_nth(ForwardIterator first, ForwardIterator last,
              std::size_t nth_index, const T& val) 
{
    first = std::find(first, last, val);
    while (nth_index-- && first != last) 
    {
        first = std::find(std::next(first), last, val);
    }
    return first;
}

template <typename RandomAccessIterator>
auto real_index(RandomAccessIterator first, RandomAccessIterator last,
                const bit_vector& sorted, std::size_t n) 
{
    auto nth_curr = find_nth(sorted.cbegin(), sorted.cend(), n, false);
    return std::next(first, std::min(std::distance(sorted.cbegin(), nth_curr),
                                     std::distance(first, last)));
}

get_destination() could be written using two std::count_if()'s, counting over the ranges (first, start], and (start+1, last].

e: Unfortunately, this solution only works if you had a bit_vector container (not std::vector<bool>) that specialized the various <algorithm> functions like a std::find() that processed 64 bits at a time rather than 1 bit at a time.

template <typename ForwardIterator, typename T>
auto find_nth(ForwardIterator first, ForwardIterator last,
              std::size_t nth_index, const T& val) 
{
    first = std::find(first, last, val);
    while (nth_index-- && first != last) 
    {
        first = std::find(std::next(first), last, val);
    }
    return first;
}

template <typename RandomAccessIterator>
auto real_index(RandomAccessIterator first, RandomAccessIterator last,
                const std::vector<bool>& sorted, std::size_t n) 
{
    auto nth_curr = find_nth(sorted.cbegin(), sorted.cend(), n, false);
    return std::next(first, std::min(std::distance(sorted.cbegin(), nth_curr),
                                     std::distance(first, last)));
}

e: Unfortunately, this solution only works if you had a real bit_vector container (not std::vector<bool>) that specialized the various <algorithm> functions like std::find().

template <typename ForwardIterator, typename T>
auto find_nth(ForwardIterator first, ForwardIterator last,
              std::size_t nth_index, const T& val) 
{
    first = std::find(first, last, val);
    while (nth_index-- && first != last) 
    {
        first = std::find(std::next(first), last, val);
    }
    return first;
}

template <typename RandomAccessIterator>
auto real_index(RandomAccessIterator first, RandomAccessIterator last,
                const bit_vector& sorted, std::size_t n) 
{
    auto nth_curr = find_nth(sorted.cbegin(), sorted.cend(), n, false);
    return std::next(first, std::min(std::distance(sorted.cbegin(), nth_curr),
                                     std::distance(first, last)));
}

I have to agree with sehe, this is well written. Just a couple of recommendations for maintainability.

Prefer standard algorithms

The immediate things that come to mind is the opportunity to use standard algorithms in your functions. real_index() could be written using std::find().

template <typename ForwardIterator, typename T>
auto find_nth(ForwardIterator first, ForwardIterator last,
              std::size_t nth_index, const T& val) 
{
    first = std::find(first, last, val);
    while (nth_index-- && first != last) 
    {
        first = std::find(std::next(first), last, val);
    }
    return first;
}

template <typename RandomAccessIterator>
auto real_index(RandomAccessIterator first, RandomAccessIterator last,
                std::vector<bool> sorted, std::size_t n) 
{
    auto nth_curr = find_nth(sorted.cbegin(), sorted.cend(), n, false);
    return std::next(first, std::min(std::distance(sorted.cbegin(), nth_curr),
                                     std::distance(first, last)));
}

get_destination() could be written using two std::count_if()'s, counting over the ranges (first, start], and (start+1, last].

Always initialize variables

RandomAccessIterator dest; // Final destination of the current element
if (positions.empty()) 
{
  dest = get_destination(first, last, compare, sorted,
                         *start, start);
}
else 
{
  dest = get_destination(first, last, compare, sorted,
                         *positions.top(), start);
}

This rule is pretty strict as it improves maintainability and protects against the used-before-set class of errors.

const auto& elem = positions.empty() ? *start : *positions.top();
RandomAccessIterator dest = get_destination(first, last, compare, sorted,
                                            elem, start);

I have to agree with sehe, this is well written. Just a couple of recommendations for maintainability.

Prefer standard algorithms

The immediate things that come to mind is the opportunity to use standard algorithms in your functions. real_index() could be written using std::find().

template <typename ForwardIterator, typename T>
auto find_nth(ForwardIterator first, ForwardIterator last,
              std::size_t nth_index, const T& val) 
{
    first = std::find(first, last, val);
    while (nth_index-- && first != last) 
    {
        first = std::find(std::next(first), last, val);
    }
    return first;
}

template <typename RandomAccessIterator>
auto real_index(RandomAccessIterator first, RandomAccessIterator last,
                const std::vector<bool>& sorted, std::size_t n) 
{
    auto nth_curr = find_nth(sorted.cbegin(), sorted.cend(), n, false);
    return std::next(first, std::min(std::distance(sorted.cbegin(), nth_curr),
                                     std::distance(first, last)));
}

get_destination() could be written using two std::count_if()'s, counting over the ranges (first, start], and (start+1, last].

Always initialize variables

RandomAccessIterator dest; // Final destination of the current element
if (positions.empty()) 
{
  dest = get_destination(first, last, compare, sorted,
                         *start, start);
}
else 
{
  dest = get_destination(first, last, compare, sorted,
                         *positions.top(), start);
}

This rule is pretty strict as it improves maintainability and protects against the used-before-set class of errors.

const auto& elem = positions.empty() ? *start : *positions.top();
RandomAccessIterator dest = get_destination(first, last, compare, sorted,
                                            elem, start);