Быстрая сортировка (Quicksort) и Сортировка слиянием (Merge Sort) — это алгоритмы сравнения, использующие стратегию "разделяй и властвуй", но различающиеся в подходах к разделению и объединению данных.
Основные отличия:
-
Подход к разделению:
- Быстрая сортировка: Выбирает опорный элемент (pivot) и разбивает массив на две части: элементы меньше опорного и элементы больше опорного. Затем рекурсивно сортирует эти части.
- Сортировка слиянием: Делит массив пополам, рекурсивно сортирует каждую половину, а затем объединяет (сливает) отсортированные половины.
-
Подход к объединению:
- Быстрая сортировка: Объединение тривиально, так как элементы уже расположены относительно опорного.
- Сортировка слиянием: Выполняет слияние отсортированных подмассивов, проходя по ним и сравнивая элементы для построения нового отсортированного массива.
-
Стабильность:
- Быстрая сортировка: Не является стабильной сортировкой (может менять относительный порядок равных элементов).
- Сортировка слиянием: Является стабильной сортировкой.
-
Используемая память:
- Быстрая сортировка: Обычно сортировка на месте (in-place), но требует рекурсивного стека. В худшем случае O(log n) для стека, в случае плохого выбора опорного элемента O(n).
- Сортировка слиянием: Обычно требуется дополнительная память O(n) для временного массива при слиянии.
-
Производительность:
| Случай | Быстрая сортировка | Сортировка слиянием |
|---|
| В среднем | O(n log n) | O(n log n) |
| В худшем | O(n^2) | O(n log n) |
| В лучшем | O(n log n) | O(n log n) |
-
Реализация:
- Быстрая сортировка: Реализация может варьироваться в зависимости от выбора опорного элемента и метода разбиения.
- Сортировка слиянием: Реализация более прямолинейна.
Пример работы (псевдокод):
python