Пірамідальне сортування (Heapsort)

Коротко: Heapsort сортує, перетворюючи дані на max-купу й потім багаторазово переміщуючи найбільший елемент у кінець.

Докладніше: Вона завжди працює за O(n log n), навіть у найгіршому разі, і не потребує додаткової пам’яті. На практиці, проте, зазвичай повільніша за швидке сортування, бо читає пам’ять стрибками, а не лінійно.

Подробиці

• Крок 1: Масив за O(n) перетворюється на max-купу: від середини назад кожен вузол «просівається» вниз.
• Крок 2: Корінь (найбільший елемент) міняється місцями з останнім елементом. Купа зменшується на 1, новий корінь просівається.
• Повторювати, доки купа не спорожніє. Масив тоді відсортований за зростанням.
• Властивості: не стійка, на місці (in place), не залежить від попередньої впорядкованості.
• Застосування: Як запасний варіант в introsort, якщо швидке сортування йде в надто глибоку рекурсію. Порівняйте купа й черга з пріоритетом.

Див. також: Сортування злиттям