Изменения

Создадим массив стеков для хранения стопок. При раскладывании элементов по стопкам для поиска самой левой подходящей стопки используем бинарный поиск. Соответственно, поиск самой левой стопки занимает <tex>O(log</tex> <tex>p)</tex>, где p - количество стопок (стеков). Таким образом, временная сложность раскладывания по стопкам не превышает <tex>O(n</tex> <tex>\cdot \log</tex> <tex>n)</tex>.Для получения отстортированного массива используем приоритетную очередь минимумов. На каждом шаге алгоритма необходимо извлечь из очереди стек с минимальной вершиной <tex>(O(1))</tex>, восстановить свойства очереди <tex>(O(log</tex> <tex>p)</tex>, где p - количество стеков в очереди. Снять вершину выбранного стека и вернуть его в очередь <tex>O(log</tex> <tex>p)</tex>. Получение отсортированного массива займёт <tex>O(n*\cdot log</tex> <tex>n)</tex> времени.

Таким образом, алгоритм сортировки требует <tex>n*O(n \cdot \log</tex> <tex>n)</tex> времени в худшем случае и <tex>O(n)</tex> дополнительной памяти при любом раскладе. Если диапазон, в котором могут изменяться данные, известен, временная сложность алгоритма сортировки составляет <tex>O(n</tex> <tex>\cdot \log</tex> <tex>\log</tex> <tex>n)</tex>. Такая оценка основывается на структуре данных [[Дерево ван Эмде Боаса|Дерево ван Эмде Боаса]].