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

algorithm, c++, c++11, sorting, vector

Solution

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));
}

Problem

Consider a `std::vector` `v` of `N` elements, and consider that the `n` first elements have already been sorted with`n < 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)

Original source