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)

Answer 1

Sort the other range only, and then use std::merge.

Answer 2

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

Answer 3

The optimal solution would be to sort the tail portion independently and then perform in-place merge, as described here

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.5750

The algorithm is quite convoluted and is usually regarded as "not worth the effort".

Of course, with C++ you can use readily available std::inplace_merge. However, the name of that algorithm is highly misleading. Firstly, there's no guarantee that std::inplace_merge actually works in-place. And when it is actually in-place, there's no guarantee that it is not implemented as a full-blown sort. In practice it boils down to trying it and seeing whether it is good enough for your purposes.

But if you really want to make it in-place and formally more efficient than a full sort, then you will have to implement it manually. STL might help with a few utility algorithms, but it does not offer any solid solutions of "just a few calls to standard functions" kind.

Answer 4

Using insertion sort on N - n last elements:

template <typename IT>
void mysort(IT begin, IT end) {
    for (IT it = std::is_sorted_until(begin, end); it != end; ++it) {
        IT insertPos = std::lower_bound(begin, it, *it);
        IT endRotate = it;
        std::rotate(insertPos, it, ++endRotate);
    }
}

Answer 5

The Timsort sorting algorithm is a hybrid algorithm developed by Pythonista Tim Peters. It makes optimal use of already-sorted subsegments anywhere inside the array, including in the beginning. Although you may find a faster algorithm if you know for sure that in particular the first n elements are already sorted, this algorithm should be useful for the overall class of problems involved. Wikipedia describes it as:

The algorithm finds subsets of the data that are already ordered, and uses that knowledge to sort the remainder more efficiently.

In Tim Peters' own words,

It has supernatural performance on many kinds of partially ordered arrays (less than lg(N!) comparisons needed, and as few as N-1), yet as fast as Python's previous highly tuned samplesort hybrid on random arrays.

Full details are described in this undated text document by Tim Peters. The examples are in Python, but Python should be quite readable even to people not familiar with its syntax.

Answer 6

Use std::partition_point (or is_sorted_until) to find n. Then if n-m is small do an insertion sort (linear search+std::rotate).

Answer 7

I assume that your question has two aims:

• improve runtime (using a clever way)
• with few effort (restricting to STL)

Considering these aims, I'd strongly recommend against this specific optimization, unless you are sure that the effort is worth the benefit. As far as I remember, std::sort() implements the quick sort algorithm, which is almost as fast on presorted input as to determine, if / how-much-of the input is sorted.

Instead of meddling with std::sort you can try changing the data structure to a sorted/prioritized queue.