Изменения

Алгоритм частично упорядочивает массив, строя на нем два раза кучу: один раз передвигая меньшие элементы влево, второй раз передвигая большие элементы вправо.Затем к массиву применяетсяДосортировав массив [[Сортировка вставками|сортировкой сортировка вставками]], можно получить временную сложность которая при почти отсортированных данных работает за <tex>O(n)</tex> в лучшем случае.

Сортировка кучей обладает двумя большими недостаткамиДостоинства:*Невозможность использования кэшаВ отличии от сортировки кучей, так как наше движение по массиву в чем-то похоже на хаотичное.*На почти отсортированных массивах работает столь же долгобыстрее, как и чем на хаотических данныхслучайных.*В силу использования сортировки вставками, которая просматривает элементы последовательно, использование кэша гораздо эффективнее.Недостатки:Так как *На длинных массивах, возникают плохо отсортированные последовательности в Jsort на последнем этапе используется сортировка вставкамисередине массива, то это частично решает проблемы что приводит к ухудшению работы сортировки кучей. Почти отсортированные данные сортируются за линейное времявставками.

 Необходимо отсортировать массив.Построим невозрастающую кучу для минимума на этом массиве.

Теперь построим на этом же массиве кучу так, чтобы немного упорядочить правую часть массива. Эта куча должна быть неубывающей кучей для максимума и быть "зеркальной" к массиву, то есть чтобы ее корень соответствовал последнему элементу массива.Получившийся почти отсортированный массив досортируем сортировкой К получившемуся массиву применим сортировку вставками.

Таким образом в худшем случае сложность JSort является <tex>O(n^2)</tex>, а в лучшем <tex>O(n)</tex>.

Построим на этом массиве невозрастающую кучудля минимума:

Построим теперь зеркальную неубывающую кучу для максимума на этом же массиве.