Сортировка слиянием (Фон Неймана)

Привет! Сегодня я расскажу тебе про один из самых красивых и полезных алгоритмов сортировки — сортировку слиянием.

Её придумал известный математик и программист Джон фон Нейман. Суть алгоритма в том, чтобы разделить задачу на более маленькие подзадачи, решить их, а затем объединить результат. Это как если бы мы захотели рассортировать стопку карточек: сначала делим её на две части, сортируем каждую по отдельности, а затем аккуратно объединяем в одну отсортированную.

Такой подход называется стратегией «разделяй и властвуй».

Как работает алгоритм

1. Если массив очень маленький (0 или 1 элемент), то он уже отсортирован.
2. Разделяем массив на две половины.
3. Сортируем каждую половину рекурсивно (то есть вызываем ту же функцию сортировки).
4. Сливаем два отсортированных массива в один с помощью алгоритма слияния, о котором мы уже говорили.

Важный момент

Для слияния массивов нам нужен дополнительный буфер (временный массив), в который мы записываем результат. Это и есть главный минус сортировки слиянием — требуется больше памяти, чем для квадратичных сортировок.

Сложность

Алгоритм делает:

• log₂n делений массива (так как на каждом шаге мы делим его пополам),
• и на каждом уровне выполняется O(n) операций для слияния.

Итого:

O(n⋅log2​n)

Это в разы быстрее, чем O(n²) у квадратичных сортировок.

Реализация на Python (список)

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])  # берём элемент из left
            i += 1
        else:
            result.append(right[j])  # берём элемент из right
            j += 1

    # добавляем оставшиеся элементы
    result.extend(left[i:])
    result.extend(right[j:])
    return result

def merge_sort(arr):
    """Сортировка слиянием (рекурсивно)"""
    if len(arr) < 2:
        return arr  # массив длиной 0 или 1 уже отсортирован

    mid = len(arr) // 2  # находим середину
    left = merge_sort(arr[:mid])   # сортируем левую половину
    right = merge_sort(arr[mid:])  # сортируем правую половину
    return merge(left, right)      # сливаем две части

# Пример
data = [4, 2, 6, 1, 5, 3, 9, 7]
print(merge_sort(data))  # [1, 2, 3, 4, 5, 6, 7, 9]

Реализация на NumPy

import numpy as np

def merge_numpy(left, right):
    """Слияние двух отсортированных массивов NumPy"""
    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 np.array(result)

def merge_sort_numpy(arr):
    """Сортировка слиянием (NumPy)"""
    if len(arr) < 2:
        return arr

    mid = len(arr) // 2
    left = merge_sort_numpy(arr[:mid])
    right = merge_sort_numpy(arr[mid:])
    return merge_numpy(left, right)

# Пример
data_np = np.array([4, 2, 6, 1, 5, 3, 9, 7])
print(merge_sort_numpy(data_np))  # [1 2 3 4 5 6 7 9]

Итог

• Сортировка слиянием работает за O(n log n).
• Требует дополнительную память для буфера.
• Является одной из самых популярных сортировок (например, используется в СУБД и некоторых языках программирования).