В чем заключается отличие быстрой сортировки от сортировки слияния?

Быстрая сортировка (Quicksort) и Сортировка слиянием (Merge Sort) — это алгоритмы сравнения, использующие стратегию "разделяй и властвуй", но различающиеся в подходах к разделению и объединению данных.

Основные отличия:

1. Подход к разделению:

   • Быстрая сортировка: Выбирает опорный элемент (pivot) и разбивает массив на две части: элементы меньше опорного и элементы больше опорного. Затем рекурсивно сортирует эти части.
   • Сортировка слиянием: Делит массив пополам, рекурсивно сортирует каждую половину, а затем объединяет (сливает) отсортированные половины.

2. Подход к объединению:

   • Быстрая сортировка: Объединение тривиально, так как элементы уже расположены относительно опорного.
   • Сортировка слиянием: Выполняет слияние отсортированных подмассивов, проходя по ним и сравнивая элементы для построения нового отсортированного массива.

3. Стабильность:

   • Быстрая сортировка: Не является стабильной сортировкой (может менять относительный порядок равных элементов).
   • Сортировка слиянием: Является стабильной сортировкой.

4. Используемая память:

   • Быстрая сортировка: Обычно сортировка на месте (in-place), но требует рекурсивного стека. В худшем случае O(log n) для стека, в случае плохого выбора опорного элемента O(n).
   • Сортировка слиянием: Обычно требуется дополнительная память O(n) для временного массива при слиянии.

5. Производительность:

   Случай	Быстрая сортировка	Сортировка слиянием
   В среднем	O(n log n)	O(n log n)
   В худшем	O(n^2)	O(n log n)
   В лучшем	O(n log n)	O(n log n)

6. Реализация:

   • Быстрая сортировка: Реализация может варьироваться в зависимости от выбора опорного элемента и метода разбиения.
   • Сортировка слиянием: Реализация более прямолинейна.

Пример работы (псевдокод):

# Быстрая сортировка
def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2] # Выбор опорного элемента
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

# Сортировка слиянием
def mergesort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = mergesort(arr[:mid]) # Рекурсивно сортируем левую половину
    right = mergesort(arr[mid:]) # Рекурсивно сортируем правую половину
    return merge(left, right) # Сливаем отсортированные половины

def merge(left, right):
    result = []
    i, j = 0, 0
    while i < len(left) and j < len(right): # Слияние
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result