Почему для стандартной сортировки выбрана Quick Sort?

Question

[askogorev]

Добрый день, достаточно много где (например STL) в качестве стандартной сортировки выбрана сортировка qsort. Вопрос - почему?

Вот статья про сортировки: http://en.wikipedia.org/wiki/Sorting_algorithm
Видно, что, например, пирамидальная сортировка (Heapsort) имеет в худшем случае сложность n*log(n), а qsort все n^2. Так почему же именно qsort?

Answer 1

[forgotten]

Потому что у qsort лучший коэффициент при n*log(n)

Answer 2

[JSinga]

Не читайте википедию, читайте подлинник - Кормен, прочитать все равно надо, пригождается чтобы там ни было))

Стоит ли говорить что это книга из разряда "обязательной к прочтению".

Если понравится можно углубиться - Кнут

Answer 3

[nekipelov]

У пирамидальной сортировки всегда O(n log n). А quck sort зачастую сортирует быстрее. Но не всегда, поэтому в STL используется Introsort.

Answer 4

[Игорь]

Она оптимальна для большинства типовых задач. Оптимальна не значит самая быстрая, значит что решает задачу в приемлемое время.
Например:

Timsort — гибридный алгоритм сортировки.
Основная идея алгоритма в том, что в реальном мире сортируемые массивы данных часто содержат в себе упорядоченные подмассивы. На таких данных Timsort существенно быстрее многих алгоритмов сортировки