Одним из основных источников эффективности быстрой сортировки является местность отсчета , где аппаратное обеспечение компьютера оптимизировано таким образом, что доступ к расположениям памяти, расположенным рядом, имеет тенденцию быть быстрее, чем доступ к расположениям памяти, разбросанным по всей памяти , Шаг разделения в быстрой сортировке обычно имеет отличную локализацию, поскольку он обращается к последовательным элементам массива около передней и задней частей. В результате быстрая сортировка имеет тенденцию работать намного лучше, чем другие алгоритмы сортировки, такие как heapsort, даже если она часто выполняет примерно одинаковое количество сравнений и перестановок, поскольку в случае heapsort доступы более разбросаны.
Кроме того, быстрая сортировка обычно намного быстрее, чем другие алгоритмы сортировки, потому что она работает на месте, без необходимости создавать какие-либо вспомогательные массивы для хранения временных значений. По сравнению с чем-то вроде сортировки слиянием, это может быть огромным преимуществом, потому что время, необходимое для выделения и освобождения вспомогательных массивов, может быть заметно. Работа на месте также улучшает месторасположение быстрой сортировки.
При работе со связанными списками ни одно из этих преимуществ не обязательно применяется. Поскольку ячейки связанного списка часто разбросаны по всей памяти, локальный бонус к доступу к соседним ячейкам связанного списка отсутствует. Следовательно, одно из огромных преимуществ быстродействия съедено. Точно так же преимущества работы на месте больше не применяются, поскольку алгоритм связанного списка сортировки слиянием не требует дополнительного пространства для хранения.
Тем не менее, быстрая сортировка все еще очень быстро в связанных списках. Сортировка слиянием имеет тенденцию быть быстрее, потому что она более равномерно разделяет списки пополам и выполняет меньше операций на итерацию, чтобы выполнить слияние, чем делать шаг разделения.
Надеюсь, это поможет!