How to partially sort in a stable way

Question

Is std::partial_sort stable and if not, is there a stable partial sort provided by the standard library or e.g. boost?

Answer 1

partial_sort is efficient and easy to provide because it is basically a quicksort where recursions that aren't necessary for the desired range are skipped. There is no equivalent efficient partial stable sort algorithm; stable_sort is usually implemented as a merge sort, and merge sort's recursion works the wrong way.

If you want a partial sort to be stable, you need to associate position information with each element. If you have a modifiable zip range you can do that by zipping together the elements and a iota vector, but modifiable zip ranges are actually impossible to build within the current iterator concepts, so it's easier to do indirect sorting via iterators and rely on the iterators' ordering. In other words, you can do this:

using MyThingV = std::vector<MyThing>;
using MyThingIt = typename MyThingV::iterator;
MyThingV things;
// Set up a vector of iterators. We'll sort that.
std::vector<MyThingIt> sorted; sorted.reserve(things.size());
for (auto it = things.begin(); it != things.end(); ++it) sorted.push_back(it);

std::partial_sort(sorted.begin(), sorted.begin() + upto_index, sorted.end(),
  [](MyThingIt lhs, MyThingIt rhs) {
    // First see if the underlying elements differ.
    if (*lhs < *rhs) return true;
    if (*rhs < *lhs) return false;
    // Underlying elements are the same, so compare iterators; these represent
    // position in original vector.
    return lhs < rhs;
  });

Now your base vector is still unsorted, but the vector of iterators is sorted the way you want.