Изменения
добавлено описание JSort
|style="background-color:#FFF;padding:2px 10px"| Массив отсортирован
|}
= JSort =
'''JSort''' является модификацией сортировки кучей, которую придумал Джейсон Моррисон (''Jason Morrison'').
Если построить на массиве последовательно 2 кучи (невозрастающую и неубывающую), это значительно упорядочит его.
Досортировав его [[Сортировка вставками|сортировкой вставками]], можно получить временную сложность <tex>O(n)</tex> в лучшем случае.
=== Алгоритм ===
Необходимо отсортировать массив. Построим невозрастающую кучу на этом массиве.
Тогда наименьший элемент окажется на первой позиции, а левая часть массива окажется почти отсортированной, так как ей будут соответствовать верхние узлы кучи.
Теперь построим на этом же массиве кучу так, чтобы немного упорядочить правую часть массива. Эта куча должна быть неубывающей и быть "зеркальной" к массиву, то есть чтобы ее корень соответствовал последнему элементу массива.
Получившийся почти отсоротированный массив досортируем сортировкой вставками.
=== Сложность ===
Постройка кучи занимает <tex>O(n)</tex>.
Сортировка вставками может отсортировать массив за <tex>O(n)</tex> в лучшем случае, и за <tex>O(n^2)</tex> в худшем.
Таким образом временная сложность JSort является <tex>O(n^2)</tex>.
*[http://ru.wikipedia.org/wiki/%D0%9F%D0%B8%D1%80%D0%B0%D0%BC%D0%B8%D0%B4%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0 Пирамидальная сортировка - Википедия]
*[http://en.wikipedia.org/wiki/Heapsort Heapsort - Wikipedia]
*[http://en.wikipedia.org/wiki/JSort JSort - Wikipedia]
*[http://habrahabr.ru/post/221095/ Описание сортировки кучей и JSort - Хабрахабр]
== Литература ==
