Кратко — основное различие сводится к трём свойствам: асимптотика $средняя/худшая$, потребление дополнительной памяти и практическая скорость $кэш‑локализация,числоперестановок,поведениеприравныхключахичастичноупорядоченныхданных$. Ниже — подробное сравнение и рекомендации по применению.

1) Быстродействие и гарантии времени выполнения

Quicksort

Среднее время: O$nlogn$.Худший случай: O$n^2$ $например,упорядоченныйвходиплохойвыборопорногоэлемента$.Рандомизация/медиана‑трёх/Introsort $переходнаheapsortприглубокойрекурсии$ дают практически гарантированный O$nlogn$.Доп. память: обычно in‑place, стековая рекурсия O$logn$ в среднем, в худшем — O$n$ без оптимизаций.Вывод: очень быстрый в среднем, но требует мер предосторожности против худшего случая.

Mergesort

Среднее и худшее: O$nlogn$ $гарантированно$.Доп. память: O$n$ на временный буфер при сортировке массивов; для связных списков можно сделать устойчивый варианта с O$1$ дополнительной памяти.Вывод: предсказуемое время, стабильный вариант $сохранениепорядкаравныхключей$, хорош для внешней/параллельной сортировки.

Heapsort

Среднее и худшее: O$nlogn$ $гарантированно$.Доп. память: O$1$ $in‑place$.Вывод: строгий гарант по худшему случаю и минимум доп. памяти, но в практике медленнее QuickSort и MergeSort из‑за худшей кэш‑локализации и большего числа обменов.

2) Практическая производительность $почемуодинбыстреедругого$

Quicksort обычно быстрее из‑за:
Отличной кэш‑локализации $работаетналокальныхчастяхмассива$.Меньшего числа сравнений/перестановок в среднем.Возможности оптимизаций $медиана‑трёх,3‑waypartitionдлямножестваравныхключей,победительвставкамидлямалыхподмассивов$.Mergesort:
Читает и пишет последовательно при слиянии — это выгодно при внешней сортировке и на современных дисках/SSD.Более предсказуемая производительность, выигрывает при частично упорядоченных данных $вчастности,TimSort—естественная/сигнатурнаяверсияmergesort—используетдлинные«runs»ичрезвычайноэффективен$.Heapsort:
Плохая кэш‑локализация: много обращений по разным индексам.Большое число сравнений и движений по сравнению с QuickSort.Зато минимальная дополнительная память и детерминированное худшее время — пригодно, когда это критично.

3) Другие важные свойства

Стабильность:
Mergesort — стабильный $приреализациисдоп.буфером$.Quicksort и Heapsort — обычно нестабильные $существуютстабильныеварианты,ноонидороже$.Поведение при многих равных ключах:
3‑way Quicksort $Датско‑нидерландскаясортировка$ — очень хорош для многих равных ключей.Обычный Quicksort без 3‑way разбиения страдает.Параллелизация:
Mergesort легко распараллеливается $независимыеслияния$.Quicksort тоже можно распараллеливать по частям, но баланс разбиения важен.Вложенность/рекурсия:
Quicksort требует контроля глубины рекурсии $Introsort$.Mergesort легко реализовать итеративно $bottom‑up$.Внешняя сортировка:
Mergesort $k‑waymerge$ — стандартный выбор для сортировки на диске/внешних данных.

4) Когда какой алгоритм предпочесть $практическиесценарии$

Quicksort $илиIntrosortкакегобезопасныйвариант$

В большинстве in‑memory случаев для массивов/векторов, когда нужна максимальная скорость.Когда память на O$n$ недоступна или нежелательна, но средняя производительность важнее худшего случая.Для данных без большого числа одинаковых ключей, либо с рандомизированным/медианным выбором опорного элемента.Практический пример: std::sort в C++ $Introsort$ — хороший универсал.

Mergesort $илиTimSort$

Когда нужна стабильность $сохранениепорядкаравныхключей$.Для внешней сортировки и больших объёмов, читаемых/записываемых последовательно.Когда данные частично упорядочены — TimSort даёт существенный выигрыш.Для сортировки связных списков $простаястабильнаяреализациябездоп.O(n)памяти$.Пример: std::stable_sort в C++, Java использует TimSort для объектов.

Heapsort

Когда строго важны гарантии худшего времени O$nlogn$ и/или допустима только O$1$ доп. память.В сценариях с ограниченной памятью и где неприемлема вероятность квадратичной работы.Реже используется на “обычных” данных из‑за медленной практической скорости, но полезен в системном коде, где нужно предсказуемое поведение.

5) Практические советы и гибриды

Используйте Introsort: Quicksort + switch to Heapsort при слишком глубокой рекурсии — сочетает скорость и гарантию O$nlogn$.Для массивов с множеством одинаковых ключей применяйте 3‑way partitioning.Для малых подмассивов переключайтесь на Insertion Sort $обычнаяоптимизация$.Для стабильной и быстрой сортировки частично упорядоченных данных — TimSort.Для внешней/дисковой сортировки — k‑way Mergesort.

Краткие рекомендации по выбору

Нужна максимальная скорость в памяти, нет требования стабильности: Introsort $реализациянаосновеQuicksort$.Нужна стабильность или внешняя сортировка / хорошие свойства на частично упорядоченных входных данных: Mergesort / TimSort.Нужны жёсткие гарантии по времени и минимум доп. памяти: Heapsort.

Если хотите, могу привести численные сравнения $сравнениеколичествасравнений/перестановок,примерысоревнованийнаразныхтипахданных$ или показать псевдокод оптимизированных вариантов $3‑wayquicksort,introsort,bottom‑upmergesort$.