Почему быстрая сортировка в среднем быстрее, чем у других?

Question

Как мы знаем, производительность быстрой сортировки в среднем равна O (n * log (n)), а производительность слияния и динамической сортировки - в среднем O (n * log (n)).Поэтому вопрос в том, почему быстрая сортировка в среднем быстрее.

Answer 1

Википедия предлагает :

Как правило, быстрая сортировка на практике значительно быстрее, чем другие алгоритмы O (nlogn), поскольку ее внутренний цикл может быть эффективно реализован на большинстве архитектур, ив большинстве реальных данных возможно сделать выбор проекта, который минимизирует вероятность необходимости квадратичного времени.Кроме того, быстрая сортировка имеет тенденцию превосходно использовать иерархию памяти, используя превосходные преимущества виртуальной памяти и доступных кэшей.Хотя быстрая сортировка не является сортировкой на месте и использует вспомогательную память, она очень хорошо подходит для современных компьютерных архитектур.

Также посмотрите на сравнение с другими алгоритмами сортировки нана той же странице.

См. также Почему быстрая сортировка на практике лучше, чем другие алгоритмы сортировки? на сайте CS.

Answer 2

Наихудший случай для быстрой сортировки на самом деле хуже, чем heapsort и mergesort, , но быстрая сортировка в среднем быстрее.

Что касается того, почему объяснение потребуется, и поэтому я буду ссылатьсяto Skiena, Руководство по разработке алгоритма.

Цитата, которая суммирует быструю сортировку против слияния / heapsort:

Когда сталкиваются с алгоритмами такой же асимптотической сложности,детали реализации и системные особенности, такие как производительность кеша и объем памяти, вполне могут оказаться решающим фактором.Что мы можем сказать, так это то, что эксперименты показывают, что если правильно реализованная быстрая сортировка реализована хорошо, она обычно в 2-3 раза быстрее, чем mergesort или heapsort.Основная причина в том, что операции в самом внутреннем цикле проще.Но я не могу с вами спорить, если вы мне не верите, когда я говорю, что быстрая сортировка быстрее.Это вопрос, решение которого лежит за пределами аналитических инструментов, которые мы используем.Лучший способ понять это - реализовать как алгоритмы, так и эксперимент.

Answer 3

Timsort может быть вариантом лучше , так как он оптимизирован для вида данных, видимых при сортировке в целом, на языке Python, где данные часто содержат встроенные «прогоны» предварительно отсортированных Предметы. В последнее время он также был принят Java.