Сортировка слиянием

Сортировка слиянием (Merge Sort): стратегия «разделяй и властвуй», рекурсия, слияние двух отсортированных половин, код на Python, сложность O(n log n).

Сортировка слиянием использует принцип «разделяй и властвуй»: делит массив пополам, рекурсивно сортирует каждую половину, а затем сливает две упорядоченные части в одну.

Сложность: O(n log n) во всех случаях; O(n) дополнительной памяти.

Идея алгоритма

Представь стопку листов с числами. Делишь её пополам. Каждую половину снова делишь — и так до тех пор, пока не останутся стопки по одному листу (один лист всегда «упорядочен»). Затем сливаешь пары стопок, каждый раз беря наименьшее из двух вершин. В итоге получаешь одну полностью отсортированную стопку.

Пошаговый разбор

Массив [38, 27, 43, 3, 9, 82, 10]:

Разбивка:
[38, 27, 43, 3, 9, 82, 10]
[38, 27, 43]    [3, 9, 82, 10]
[38] [27,43]    [3,9] [82,10]
[38] [27][43]   [3][9] [82][10]

Слияние:
[27,43]  [3,9]  [10,82]
[27,38,43]      [3,9,10,82]
       [3,9,10,27,38,43,82]

Код

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


data = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(data))

Вывод:

[3, 9, 10, 27, 38, 43, 82]

Сложность и свойства

Случай	Время	Память
Лучший	O(n log n)	O(n)
Средний	O(n log n)	O(n)
Худший	O(n log n)	O(n)

Алгоритм устойчивый: при слиянии одинаковые элементы берутся из левой половины первыми (условие <=). Требует O(n) дополнительной памяти для вспомогательных массивов — это его главный недостаток.

Почему O(n log n)? На каждом уровне рекурсии суммарная работа — O(n) (слияние). Уровней рекурсии — log₂n (столько раз делим пополам). Итого: n · log n.

Когда применять

Нужна гарантированная O(n log n) сортировка — merge sort не деградирует в O(n²) как quick sort.
Требуется устойчивость (например, сортировка объектов по нескольким полям).
Сортировка связных списков — для них merge sort предпочтительнее quick sort.
Данные не помещаются в память — внешняя сортировка основана на идее слияния.

Коротко

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