How to partially sort in steady mode

partial_sort

efficient and easy to provide as it is basically quicksort where recursions that are not needed for the required range are skipped. There is no equivalent efficient partial stable sorting algorithm; stable_sort

is usually implemented as a merge sort, and the merge sort recursion does not work correctly.

If you want the partial sort to be stable, you need to associate location information with each item. If you have a modifiable zip range, you can do so by concatenating the elements and the iota vector, but the modifiable zip ranges are actually not possible to construct within existing iterator concepts, so it's easier to do indirect sorting with iterators and rely on iterators "orders. Others in 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 iterator vector is sorted the way you want.