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

Быструю сортировку мы уже разобрали: она выбирает опорный элемент и расставляет остальные вокруг него. У неё есть слабое место — в худшем случае (например, если список уже почти отсортирован, а опорный элемент выбран неудачно) она работает медленно, за O(n²). Сортировка слиянием устроена иначе: она никогда не зависит от того, какие именно числа в списке и в каком порядке они стоят. Она всегда делит список ровно пополам, поэтому всегда укладывается в O(n log n), без исключений. Это цена и выгода одновременно: придётся завести дополнительную память под промежуточные списки, зато скорость предсказуема всегда.

Идея: разделяй и властвуй

Простыми словами. Представьте, что вам дали большую нерасставленную по алфавиту стопку карточек. Расставлять сразу всю стопку неудобно. Но если разделить её на две стопки поменьше, расставить каждую по отдельности, а потом аккуратно слить две уже расставленные стопки в одну — получится быстрее и надёжнее. А если делить дальше, до стопок по одной карточке, расставлять вообще не придётся: одна карточка уже стоит на своём месте сама по себе. Дальше остаётся только правильно сливать стопки обратно, по две.

Официальный термин. Такой приём в программировании называется divide and conquer (разделяй и властвуй): большая задача рекурсивно разбивается на более мелкие копии самой себя, пока они не станут тривиальными, а потом решения мелких задач объединяются в решение исходной. Сортировка, построенная на этом приёме, называется сортировкой слиянием (merge sort). У неё два этапа: деление — список рекурсивно режется пополам, пока не останутся списки из одного элемента (список из одного элемента уже отсортирован по определению); и слияние — отсортированные половины сливаются в один отсортированный список, элемент за элементом.

Слияние двух отсортированных списков

Простыми словами. Представьте две стопки карточек, каждая уже расставлена по возрастанию, и лежат они лицом вверх, а вы видите только верхнюю карточку каждой стопки. Чтобы слить их в одну, вы всё время сравниваете две верхние карточки и забираете меньшую в общую стопку. Когда одна из стопок закончится, вы просто сгребаете весь остаток второй стопки — сравнивать больше не с чем, там и так уже по порядку.

Официальный термин. Такое слияние называют двухуказательным (two pointers): заводятся два индекса — по одному на каждый список, они показывают, докуда список уже разобран. На каждом шаге сравнивается элемент под одним указателем с элементом под другим, меньший переносится в результат, и указатель у него сдвигается на шаг вперёд.

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

Разберём эту функцию по частям.

• def merge(left, right): — функция принимает два списка, left и right, каждый уже отсортирован по возрастанию. Это условие важно: функция не сортирует их с нуля, она только сливает.
• result = [] — сюда будем складывать итоговый отсортированный список.
• i, j = 0, 0 — два указателя. i показывает, какой элемент left сравнивается следующим, j — то же самое для right. Оба начинают с нуля, то есть с первого элемента каждого списка.
• while i < len(left) and j < len(right): — цикл работает, пока в ОБОИХ списках остались несравненные элементы. Как только один список закончится, условие станет ложным и цикл остановится.
• if left[i] <= right[j]: — сравниваем текущий элемент left с текущим элементом right. Знак <=, а не просто <, выбран специально: при равенстве элемент из left идёт первым, это делает сортировку стабильной (одинаковые элементы не меняются местами друг с другом).
• result.append(left[i]) и i += 1 — если элемент left меньше или равен, он меньше подходит для текущего места в результате, поэтому забираем его и сдвигаем указатель i на следующий элемент left.
• else: result.append(right[j]) и j += 1 — иначе меньше элемент из right, забираем его и сдвигаем j.
• result.extend(left[i:]) — когда цикл закончился, один из списков мог остаться неразобранным. left[i:] — срез от текущего i до конца списка, то есть всё, что не успели забрать. extend добавляет все эти элементы в конец result разом (в отличие от append, который добавил бы весь список как один элемент).
• result.extend(right[j:]) — то же самое для остатка right. На практике сработает только одна из этих двух строк: та, чей список ещё не был разобран целиком, у второй срез окажется пустым и extend ничего не добавит.
• return result — возвращаем готовый слитый список.

Проверим на примере: merge([3, 27], [9, 10, 38]). Сначала i=0, j=0: сравниваем 3 и 9, забираем 3, i=1. Сравниваем 27 и 9, забираем 9, j=1. Сравниваем 27 и 10, забираем 10, j=2. Сравниваем 27 и 38, забираем 27, i=2. Список left закончился (i == len(left)), цикл останавливается. left[2:] — пустой срез, right[2:] равен [38], он дописывается в конец. Итог: [3, 9, 10, 27, 38].

Полная сортировка: merge_sort()

Простыми словами. Функция merge() умеет сливать только уже отсортированные списки. Чтобы получить отсортированные половины, с которых можно начать, применим тот же приём деления к каждой половине снова, и снова, пока список не сократится до одного элемента — а список из одного элемента отсортирован всегда, сравнивать там нечего. Это тот самый рекурсивный вызов функции самой себя, с которым мы уже встречались: функция решает большую задачу, вызывая саму себя на меньшей версии этой же задачи.

Официальный термин. Про рекурсию мы уже говорили: у любой рекурсивной функции есть базовый случай — условие, при котором функция отвечает сразу, без нового вызова себя, и рекурсивный случай — вызов функции с меньшим по объёму аргументом. Для сортировки слиянием базовый случай — список длиной 0 или 1, рекурсивный — список делится на left и right, каждая половина сортируется тем же merge_sort(), а затем результаты сливаются функцией merge().

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)

• if len(arr) <= 1: return arr — базовый случай. Список из нуля или одного элемента уже отсортирован, его незачем ни делить, ни сливать — просто возвращаем как есть. Без этой строки рекурсия делила бы список бесконечно, до ошибки переполнения стека.
• mid = len(arr) // 2 — вычисляем середину списка, целочисленным делением. Например, для списка длиной 7 mid будет равен 3.
• left = merge_sort(arr[:mid]) — arr[:mid] — срез, левая половина списка, от начала до середины (не включая её). Функция вызывает саму себя на этой половине — это и есть рекурсивный вызов. Результат, уже отсортированную половину, сохраняем в left.
• right = merge_sort(arr[mid:]) — то же самое для правой половины, от середины до конца.
• return merge(left, right) — когда обе половины отсортированы (это гарантирует рекурсия — она не вернёт управление сюда, пока сама себя не отработает до конца), сливаем их функцией из предыдущего раздела и возвращаем результат.

Проследим вызовы для merge_sort([38, 27, 43, 3]). Список делится на [38, 27] и [43, 3]. Каждый из них делится ещё раз: [38, 27] на [38] и [27], [43, 3] на [43] и [3]. Списки из одного элемента — базовый случай, они возвращаются как есть. Дальше идёт слияние, с самого нижнего уровня: merge([38], [27]) даёт [27, 38], merge([43], [3]) даёт [3, 43]. Последний вызов, merge([27, 38], [3, 43]), даёт итоговый [3, 27, 38, 43].

Сложность и сравнение с быстрой сортировкой

Простыми словами. У быстрой сортировки скорость зависит от того, насколько удачно выбран опорный элемент: не повезёт с данными — будет медленно. У сортировки слиянием такой зависимости нет: она всегда делит список ровно пополам, независимо от того, какие в нём числа и в каком порядке. Поэтому её скорость одинаковая что для случайного списка, что для почти отсортированного, что для отсортированного в обратном порядке.

Официальный термин. Временная сложность сортировки слиянием — O(n log n) и в лучшем, и в среднем, и в худшем случае: она делит список на log n уровней (каждый уровень делит объём пополам), и на каждом уровне сливает суммарно n элементов. У быстрой сортировки средний случай тоже O(n log n), но худший — O(n²). Платить за стабильность приходится памятью: сортировка слиянием создаёт новые списки при каждом слиянии, поэтому требует O(n) дополнительной памяти, тогда как быстрая сортировка перестраивает список на месте, почти без лишней памяти.

Частые ошибки

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

while i < len(left) and j < len(right):
    ...
return result

Что важно запомнить

• Сортировка слиянием работает по принципу «разделяй и властвуй»: делит список пополам, пока не останутся одиночные элементы, затем сливает их обратно по порядку.
• Функция merge(left, right) сливает два уже отсортированных списка через два указателя, сравнивая текущие элементы и забирая меньший; знак <= делает слияние стабильным.
• После цикла в merge() обязательно дописывается остаток того списка, что не разобрался до конца, через extend().
• Функция merge_sort(arr) рекурсивно делит список срезами arr[:mid] и arr[mid:], базовый случай — список длиной 0 или 1.
• Сложность сортировки слиянием — O(n log n) всегда, без худшего случая, в отличие от быстрой сортировки. Плата за это — O(n) дополнительной памяти под промежуточные списки.