Сортировка log (n) отсортированных подпоследовательностей в O (n log log n)

Question

У меня есть log (n) попарно отсортированных подпоследовательностей (которые могут различаться по длине), которые мне нужно отсортировать в O (n log log n), но я не могу понять, как. Я думал об использовании сортировки слиянием, но это имеет временную сложность O (n log n).

Answer 1

Используйте сортировку естественным слиянием снизу вверх . Если стабильность не является обязательным требованием, используйте последовательность не по порядку, чтобы указать конец цикла (код также должен использовать конец массива в качестве конца цикла). Если требуется стабильность, вам нужно будет создать второй массив счетчиков (или указателей) для отслеживания границ прогонов, чтобы не допустить, чтобы два или более прогонов рассматривались как один прогон из-за того, что во время процесса слияния два или более прогонов находятся в порядке , Поскольку начальное состояние - log (n), то естественная сортировка слиянием снизу займет log (log (n)) проходов для сложности времени O (n log (log (n)).