Эффективный способ чтобы отсортировать конкатенацию списков (STL), подсказку сортировки слиянием, частично отсортировано

У меня есть ситуация, когда я получаю список значений, которые уже частично отсортированы. В моем последнем списке N блоков, каждый блок отсортирован . Итак, у меня есть список таких данных (косая черта только для акцента):

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

У меня они в векторе в виде серии указателей на объекты. В настоящее время я просто использую std :: sort с пользовательским сравнением на сортировку. Я бы предположил, что это неоптимально, поскольку моя последовательность - некоторый вырожденный случай.

Существуют ли какие-либо другие stl-функции, подсказки или что-то еще, которые я мог бы использовать для получения оптимального вида таких данных? (Библиотеки Boost тоже подойдут).

Хотя я не могу легко разбить входные данные, я, конечно, могу определить, где начинаются подпоследовательности.