2
правки
Изменения
немного изменено описание, добавлена анимация с примером
= JSort =
'''JSort''' является модификацией сортировки кучей, которую придумал Джейсон Моррисон (''Jason Morrison'').
Досортировав массив [[Сортировка вставками|сортировкой вставками]], можно получить временную сложность <tex>O(n)</tex> в лучшем случае.
Тогда наименьший элемент окажется на первой позиции, а левая часть массива окажется почти отсортированной, так как ей будут соответствовать верхние узлы кучи.
Теперь построим на этом же массиве кучу так, чтобы немного упорядочить правую часть массива. Эта куча должна быть неубывающей и быть "зеркальной" к массиву, то есть чтобы ее корень соответствовал последнему элементу массива.
Получившийся почти отсоротированный отсортированный массив досортируем сортировкой вставками.
=== Сложность ===
Таким образом временная сложность JSort является <tex>O(n^2)</tex>.
=== Пример ===
[[Файл:JSort.gif]]
== Ссылки ==
