Мы рассмотрели далеко не все способы сортировки массивов. В частности среди рассмотренных нами алгоритмов внутренней сортировки нет алгоритма, который бы имел оценку трудоемкости O(n log n) на худший случай и не требовал бы дополнительной памяти, зависящего от n размера. Одним из таких алгоритмов является так называемая пирамидальная сортировка, для ознакомления с которой мы отсылаем читателя к списку литературы.

Литература

1. Кормен Томас X., Лейзерсон Чарльз И., Ривест Рональд Л., Штайн Клиффорд. Алгоритмы: построение и анализ, 2-е издание: Пер. с англ. – М.: Издательский дом "Вильямс", 2005. – 1296 с.
2. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ. М: МЦНМО, 2001. – 960 с.
3. Алексеев В.Е., Таланов В.А. Графы и алгоритмы. Структуры данных. Модели вычислений. М: Интернет-Университет Информационных Технологий. БИНОМ, 2006. – 320 с.
4. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов М: Мир, 1979. – 536 c.