Новый алгоритм сортировки

анонимус в институте не учился и классиков не читал? Этож самый настоящий баян, достаточно посмотреть в конце статьи ссылки

Heapsort was originally published by J.W.J. Williams as Algorithm 232 in the journal Communications of the ACM [Wil 64].

и далее

[Wil 64] J.W.J. Williams: Algorithm 232: Heapsort. Communications of the ACM, 7, 6, 347-348 (1964)

Heapsort was originally published by J.W.J. Williams as Algorithm 232 in the journal Communications of the ACM [Wil 64].

Algorithm 232: Heapsort JWJ Williams - Communications of the ACM, 1964

Новый, говоришь? Ну-ну... Слегка постарше юникса, правда - а так - да, новый...

>Новый алгоритм сортировки

значит меня на первом курсе обманули

qsort - наше все

А расскажите для чего он предназначен. В чем его специализация?

он не расходует лишней памяти в отличие от qsort. Также у него реальный n*lg(n) для худшего случая. Стандартный qsort дает n*lg(n) только в среднем. Но на практике heapsort медленнее qsort.

Интересно, почему он на практике медленнее при том что у него O(n) выходит не хуже qsort? Для какого применения(тип данных, типичная длина последовательности) это справедливо?

Млин, почитай любую книгу. У heapsort O(n*logn) с большой константой C (по сравнению с quicksort), поэтому в среднем он работает медленнее, но в худшем случае (когда quicksort не дает O(n*logn)) он быстрее quicksort.

def offtop:
    почитал "Зов Ктулху"
    про heapsort ничего не нашёл