Історія виникнення

Даний метод сортування був запропонований Дж. У. Дж. Вільямсом і Р.У. Флойдом в 1964 році. Пірамідальне сортування (воно ж сортування купою)

— класичний алгоритм який, мабуть, повинен знати будь-який програміст. Стара добра «пірамідка» примітна тим, що в незалежності від набору даних у неї одна і та ж складність за часом (причому, дуже пристойна) — O (n log n ). Кращих і вироджених випадків для неї немає.

З моменту винаходу методу (більш ніж 50 років) було чимало охочих кардинально оптимізувати процес накладання сортуючих куп.

ü Тернарне пірамідальне сортування;

ü Плавне сортування;

ü Сортування декартовим деревом.

Ось неповний список інновацій. Перераховані алгоритми хоча при тестуванні і випереджають оригінал по абсолютній швидкості хто на 12, а хто і на 25%, в оцінці тимчасової складності все одно крутяться навколо O (n log n ). При цьому дані методи досить витончено реалізовані.

Своє бачення пірамідальної сортування запропонував і скромний трудівник Університету Манітоби Джейсон Моррісон . При цьому спосіб в деяких випадках за швидкістю наближається до O (n ).