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

Question

У меня есть ситуация, когда я получаю список значений, которые уже частично отсортированы. В моем окончательном списке 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 тоже хороши).

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

Answer 1

Вы можете попробовать std::merge, хотя этот алгоритм может объединять только две отсортированные коллекции за раз, поэтому вам придется вызывать его в цикле.Также обратите внимание, что std::list предоставляет merge в качестве функции-члена.

EDIT На самом деле std::inplace_merge может быть даже лучшим кандидатом.

Answer 2

Это требует «многоканального слияния». Стандартная библиотека не имеет соответствующего алгоритма для этого. Однако параллельное расширение стандартной библиотеки GCC:

__gnu_parallel::multiway_merge.

Answer 3

Если вы можете сэкономить память, mergesort будет работать очень хорошо для этого. Для достижения наилучших результатов объединяйте две самые маленькие цепочки за раз, пока у вас не будет только одной.

Answer 4

вы можете выполнять итерацию по всем спискам одновременно, сохраняя и индексируя для каждого списка. и сравнивать только элементы в этом индексе.

это может быть значительно быстрее обычной сортировки: O (n) против O (n * log (n)), где n - количество элементов во всех списках.

см. Статью википедии .

C ++ имеет std :: merge для него, но он не будет обрабатывать несколько списков одновременно, поэтому вы можете создать свою собственную версию, которая делает.