c++ - Sort a vector in which the n first elements have been already sorted?

Question

Consider a std::vector v of N elements, and consider that the n first elements have already been sorted withn < N and where (N-n)/N is very small:

Is there a clever way using the STL algorithms to sort this vector more rapidly than with a complete std::sort(std::begin(v), std::end(v)) ?

EDIT: a clarification: the (N-n) unsorted elements should be inserted at the right position within the n first elements already sorted.

EDIT2: bonus question: and how to find n ? (which corresponds to the first unsorted element)

question from:https://stackoverflow.com/questions/21592316/sort-a-vector-in-which-the-n-first-elements-have-been-already-sorted

Answer 1

void foo( std::vector<int> & tab, int n ) {
     std::sort( begin(tab)+n, end(tab));
     std::inplace_merge(begin(tab), begin(tab)+n, end(tab));
}

for edit 2

auto it = std::adjacent_find(begin(tab), end(tab),  std::greater<int>() );
if (it!=end(tab)) {
    it++;
    std::sort( it, end(tab));
    std::inplace_merge(begin(tab), it, end(tab));
}