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

Быстрая сортировка (Quicksort) vs сортировка слиянием (Merge Sort)

Это два классических алгоритма сортировки с совершенно разными характеристиками. Хотя оба работают за O(n log n) в среднем случае, они различаются по стабильности, расходу памяти и практической производительности.

Сложность алгоритмов

Quicksort (быстрая сортировка)

• Лучший случай: O(n log n) — когда опорный элемент выбран оптимально
• Средний случай: O(n log n) — на случайных данных
• Худший случай: O(n²) — когда опорный элемент всегда минимум или максимум
• Память: O(log n) — только для рекурсивного стека вызовов

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

• Лучший случай: O(n log n) — всегда
• Средний случай: O(n log n) — всегда
• Худший случай: O(n log n) — всегда
• Память: O(n) — нужен дополнительный массив для слияния

Ключевые различия

1. Гарантированность производительности

Quicksort:

• В среднем быстрее (в 2-3 раза) за счёт меньших накладных расходов
• Может деградировать до O(n²) на плохих данных
• Используется в Python (sorted(), list.sort())

Merge Sort:

• Гарантированное O(n log n) — предсказуема всегда
• Никогда не упадёт в производительности
• Идеален, когда нужна гарантия

2. Стабильность

Quicksort: нестабилен — порядок равных элементов может изменитьсяо

# Пример нестабильности Quicksort
data = [(1, 'a'), (2, 'b'), (1, 'c'), (2, 'd')]
# После quicksort: [(1, 'c'), (1, 'a'), (2, 'd'), (2, 'b')] — порядок равных нарушен

Merge Sort: стабилен — равные элементы сохраняют исходный порядок

# Пример стабильности Merge Sort
data = [(1, 'a'), (2, 'b'), (1, 'c'), (2, 'd')]
# После merge sort: [(1, 'a'), (1, 'c'), (2, 'b'), (2, 'd')] — порядок сохранен

3. Использование памяти

Quicksort:

• O(log n) доп. памяти
• Сортирует на месте (in-place)
• Лучше для больших массивов с ограниченной памятью

Merge Sort:

• O(n) доп. памяти
• Требует копирования элементов
• Неэффективен для данных в памяти, но отлично подходит для файлов

Реализация Quicksort

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)

# Сложнее, но эффективнее (in-place версия)
def quicksort_inplace(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    
    if low < high:
        pivot_index = partition(arr, low, high)
        quicksort_inplace(arr, low, pivot_index - 1)
        quicksort_inplace(arr, pivot_index + 1, high)
    
    return arr

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

Реализация Merge Sort

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 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

Сравнительная таблица

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

Используй Quicksort для:

• Большинства практических задач (это default в Python)
• Когда памяти достаточно (O(n) для merge не критична)
• Когда не критична абсолютная гарантия на время
• Внутренней памяти (массивы, списки)
• Когда нужна максимальная скорость

Используй Merge Sort для:

• Когда нужна гарантированная O(n log n)
• Когда нужна стабильная сортировка
• Внешней памяти (файлы на диске) — можешь сортировать 1TB файл
• Параллельной обработки (легко распараллелить)
• Связных списков (не требует случайного доступа)
• Когда нужна предсказуемость

Практический пример

import time
import random

# Тест на производительность
n = 10000
arr = [random.randint(1, 1000) for _ in range(n)]

# Python использует Timsort (гибрид Merge + Insertion)
start = time.time()
sorted(arr)
end = time.time()
print(f'Timsort: {(end - start) * 1000:.3f}ms')

# Для файловых данных (streaming)
def external_merge_sort(filename):
    """Сортирует файл, помещаясь в O(log n) памяти"""
    # Читаем 1MB блоков, сортируем каждый (Quicksort), записываем
    # Затем мержим блоки (Merge Sort)
    pass

Заключение

Пython выбрал мудро: встроенная сортировка использует Timsort — гибрид Quick и Merge Sort, который даёт лучшее из обоих миров:

• O(n log n) гарантия
• Стабильность
• Отличная производительность на реальных данных

Для интервью помни: Quicksort быстрее на практике, но Merge Sort надежнее и стабильнее.