Efficient way to sort a concatenation of lists (STL), merge sort hint, partially sorted

Question

I have a situation where I get a list of values that are already partially sorted. There are N blocks in my final list, each block is sorted. So I end up having a list of data like this (slashes are just for emphasis):

1 2 3 4 5 6 7 8 / 1 2 3 4 5 / 2 3 4 5 6 7 8 9 / 1 2 3 4

I have these in a vector as a series of pointers to the objects. Currently I just use std::sort with a custom comparator to the sorting. I would guess this is sub-optimal as my sequence is some degenerate case.

Are there any other stl functions, hints, or otherwise that I could use to provide an optimal sort of such data? (Boost libraries are also fine).

Though I can't easily break up the input data I certainly can determine where the sub-sequences start.

Answer 1

You could try std::merge, although this algorithm can only merge two sorted collections at a time, so you would have to call it in a loop. Also note that std::list provides merge as a member function.

EDIT Actually std::inplace_merge might be an even better candidate.

Answer 2

This calls for a “multiway merge”. The standard library doesn’t have an appropriate algorithm for that. However, the parallel extension of the GCC standard library does:

__gnu_parallel::multiway_merge.