В чем разница между быстрой и сортировкой слиянием

Сортировка слиянием (Merge Sort)

• Стабильная, гарантированная сложность O(n log n)
• Использует дополнительную память O(n) для временных массивов
• Работает по принципу "разделяй и властвуй": рекурсивно делит массив пополам, затем сливает отсортированные части

Быстрая сортировка (Quick Sort)

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

Пример быстрой сортировки:

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)

Когда что использовать:

• Merge Sort: когда важна стабильность и гарантированное время
• Quick Sort: когда важна экономия памяти и средняя скорость