Вот реализация , которая обходит список только один раз, собирает прогоны, а затем планирует слияния таким же образом, как это делает слияние.
Сложность - O (n log m), где n - количество элементов, а m - количество прогонов. Наилучший случай - O (n) (если данные уже отсортированы), а наихудший - O (n log n), как и ожидалось.
Требуется O (log m) временной памяти; сортировка производится в списках по месту.
(обновлено ниже. Первый комментатор отмечает, что я должен описать это здесь)
Суть алгоритма:
while list not empty
accumulate a run from the start of the list
merge the run with a stack of merges that simulate mergesort's recursion
merge all remaining items on the stack
Накопление прогонов не требует особых объяснений, но полезно воспользоваться возможностью накопить как восходящие, так и нисходящие прогоны (в обратном порядке). Здесь он добавляет элементы, меньшие, чем начало цикла, и добавляет элементы, которые больше или равны концу цикла. (Обратите внимание, что для предварительной сортировки следует использовать строго меньше, чем для сохранения стабильности сортировки.)
Проще всего вставить код слияния здесь:
int i = 0;
for ( ; i < stack.size(); ++i) {
if (!stack[i])
break;
run = merge(run, stack[i], comp);
stack[i] = nullptr;
}
if (i < stack.size()) {
stack[i] = run;
} else {
stack.push_back(run);
}
Рассмотрите возможность сортировки списка (по умолчанию) (игнорируя прогоны). Состояния стека выполняются следующим образом:
[ ]
[ (d) ]
[ () (a d) ]
[ (g), (a d) ]
[ () () (a d g i) ]
[ (b) () (a d g i) ]
[ () (b e) (a d g i) ]
[ (c) (b e) (a d g i ) ]
[ () () () (a b c d e f g i) ]
[ (j) () () (a b c d e f g i) ]
[ () (h j) () (a b c d e f g i) ]
Затем, наконец, объедините все эти списки.
Обратите внимание, что количество элементов (прогонов) в стеке [i] равно нулю или 2 ^ i, а размер стека ограничен 1 + log2 (nruns). Каждый элемент объединяется один раз на уровне стека, следовательно, O (n log m) сравнений. Здесь есть некоторое сходство с Timsort, хотя Timsort поддерживает свой стек, используя что-то вроде последовательности Фибоначчи, в которой используются степени двойки.
При накоплении прогонов используются все уже отсортированные данные, поэтому сложность в лучшем случае составляет O (n) для уже отсортированного списка (один прогон). Поскольку мы накапливаем как восходящие, так и нисходящие прогоны, прогоны всегда будут иметь длину не менее 2. (Это уменьшает максимальную глубину стека как минимум на единицу, оплачивая в первую очередь затраты на поиск прогонов.) В худшем случае сложность O (n log n), как и ожидалось, для данных с высокой степенью рандомизации.
(Гм ... Второе обновление.)
Или просто посмотрите википедию на восходящий слияние .