Smoothsort

Smoothsort (Плавная сортировка) -- алгоритм сортировки, разновидность пирамидальной сортировки, разработанная Э. Дейкстрой в 1981 году. Как и пирамидальная сортировка, имеет сложность в худшем случае равную [math] O(n log n) [/math]. Преимущество плавной сортировки в том, что её сложность приближается к [math] O(n) [/math], если входные данные частично отсортированы, в то время как у пирамидальной сортировки сложность всегда одна, независимо от состояния входных данных.

Основная идея

Как и в пирамидальной сортировке, в массив накапливается куча из данных, которые затем сортируются путём непрерывного удаления максимума из кучи. В отличие от пирамидальной сортировки, здесь используется не двоичная куча, а специальная, полученная с помощью чисел Леонардо:

[math] L(0) = 1, L(1) = 1, L(i) = L(i - 1) + L(i - 2) + 1 [/math]