Сортировка слиянием: алгоритм, сложность и реализация на Python, Java и C

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

Код проверен 23.09.2026: Python 3.14.7 (и 3.9.6), OpenJDK 25.0.4, Apple clang 21 с флагами -std=c11 -Wall -Wextra.

Три свойства, которые легко перепутать

Устойчивость и «на месте» — независимые свойства: быстрая сортировка обычно работает на месте, но неустойчива, а слияние устойчиво, но требует буфер.

Как работает алгоритм: прогон на 7 числах

Возьмем массив [38, 27, 43, 3, 9, 82, 10]. Середина считается как len // 2, поэтому левая часть получает 3 элемента, правая 4.

Разделение:
[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]    [82] [10]

Слияние (снизу вверх):
[27] + [43]            -> [27, 43]
[38] + [27, 43]        -> [27, 38, 43]
[3] + [9]              -> [3, 9]
[82] + [10]            -> [10, 82]
[3, 9] + [10, 82]      -> [3, 9, 10, 82]
[27, 38, 43] + [3, 9, 10, 82] -> [3, 9, 10, 27, 38, 43, 82]

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

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

Сначала полный пример, который можно скопировать и запустить.

def merge_sort(items, key=lambda x: x):
    """Возвращает новый отсортированный список, исходный не меняет."""
    if len(items) <= 1:
        return list(items)
    mid = len(items) // 2
    left = merge_sort(items[:mid], key)
    right = merge_sort(items[mid:], key)
    return merge(left, right, key)


def merge(left, right, key):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        # <= держит равные элементы в исходном порядке (устойчивость)
        if key(left[i]) <= key(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))
print(data)

orders = [("Анна", 3), ("Борис", 1), ("Вера", 3), ("Глеб", 1)]
print(merge_sort(orders, key=lambda o: o[1]))

Вывод:

[3, 9, 10, 27, 38, 43, 82]
[38, 27, 43, 3, 9, 82, 10]
[('Борис', 1), ('Глеб', 1), ('Анна', 3), ('Вера', 3)]

Первая строка — отсортированный массив, вторая показывает, что исходный список не изменился. Третья проверяет устойчивость: заказы отсортированы по числу, и среди равных Борис остался перед Глебом, а Анна перед Верой — как во входе.

Разбор по частям:

• merge_sort отвечает только за деление и рекурсию. Глубина рекурсии около log2(n): для миллиона элементов это примерно 20 уровней, лимит рекурсии Python здесь не мешает.
• merge — единственное место, где элементы сравниваются.
• Срезы items[:mid] создают копии. Пиковая дополнительная память остается O(n), но копий много, поэтому эта версия учебная. В рабочем коде на Python берут встроенный sorted() — он тоже устойчив и написан на C.

Типичная ошибка: < вместо <= в слиянии

Если в merge написать строгое сравнение, числа по-прежнему отсортируются, но устойчивость пропадет.

        if key(left[i]) < key(right[j]):   # ошибка: при равенстве берется правый элемент

Тот же запуск дает:

[3, 9, 10, 27, 38, 43, 82]
[38, 27, 43, 3, 9, 82, 10]
[('Глеб', 1), ('Борис', 1), ('Вера', 3), ('Анна', 3)]

Числа в порядке, а заказы с равным ключом поменялись местами. На целых числах ошибку не видно, поэтому устойчивость проверяют отдельным тестом на записях с повторяющимися ключами. Исправление — вернуть <=: при равенстве первым идет элемент левой половины, то есть тот, что стоял раньше.

Сложность и память

Почему O(n log n) на любом входе: массив делится пополам, пока не останутся одиночные элементы, — это около log2(n) уровней. На каждом уровне все слияния вместе проходят по n элементам. Итого порядка n * log2(n) операций, и форма входа на это почти не влияет.

Для проверки посчитаем сравнения на 1024 элементах (n * log2(n) = 10 240) и для контраста — у наивной быстрой сортировки с первым элементом в роли опорного:

У слияния на любом входе не больше n * log2(n). Наивная быстрая сортировка на упорядоченном входе вырождается в n^2/2. Это граница именно наивного выбора опорного: библиотечные реализации выбирают его иначе и такого провала на отсортированных данных не показывают.

Про память: классическая версия для массива держит буфер на n элементов плюс стек рекурсии O(log n). Существуют варианты слияния на месте, но они заметно сложнее и на практике используются редко. O-нотация описывает рост, а не секунды: на массивах из десятков элементов простая сортировка вставками часто быстрее, поэтому библиотечные гибриды сортируют короткие куски вставками, а сливают уже их.

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

Здесь буфер выделяется один раз на всю сортировку, а не в каждом вызове, — это главное отличие от учебной версии на Python.

import java.util.Arrays;
import java.util.Random;

public class MergeSort {

    public static void sort(int[] a) {
        if (a.length < 2) return;
        int[] buf = new int[a.length];   // один буфер на всю сортировку
        sort(a, buf, 0, a.length);
    }

    // сортирует полуинтервал a[lo, hi)
    private static void sort(int[] a, int[] buf, int lo, int hi) {
        if (hi - lo < 2) return;
        int mid = lo + (hi - lo) / 2;    // без переполнения на больших индексах
        sort(a, buf, lo, mid);
        sort(a, buf, mid, hi);
        merge(a, buf, lo, mid, hi);
    }

    private static void merge(int[] a, int[] buf, int lo, int mid, int hi) {
        System.arraycopy(a, lo, buf, lo, hi - lo);
        int i = lo, j = mid, k = lo;
        while (i < mid && j < hi) {
            a[k++] = (buf[i] <= buf[j]) ? buf[i++] : buf[j++];
        }
        while (i < mid) a[k++] = buf[i++];
        // хвост правой половины уже стоит на своих местах в a
    }

    public static void main(String[] args) {
        int[] data = {38, 27, 43, 3, 9, 82, 10};
        sort(data);
        System.out.println(Arrays.toString(data));

        Random rnd = new Random(42);
        for (int t = 0; t < 1000; t++) {
            int[] x = rnd.ints(rnd.nextInt(50), -100, 100).toArray();
            int[] expected = x.clone();
            Arrays.sort(expected);
            sort(x);
            if (!Arrays.equals(x, expected)) throw new AssertionError(Arrays.toString(x));
        }
        System.out.println("1000 случайных тестов пройдено");
    }
}

Запуск одной командой java MergeSort.java (Java 11+) печатает:

[3, 9, 10, 27, 38, 43, 82]
1000 случайных тестов пройдено

Вторая часть main — простой тест: 1000 случайных массивов длиной до 50 сравниваются с результатом Arrays.sort. Остаток правой половины не копируется: когда левая исчерпана, индекс k совпадает с j, и эти элементы уже на своих местах.

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

В C важно не забыть про память: буфер берется через malloc, результат проверяется, в конце буфер освобождается.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static void merge(int *a, int *buf, size_t lo, size_t mid, size_t hi) {
    memcpy(buf + lo, a + lo, (hi - lo) * sizeof *a);
    size_t i = lo, j = mid, k = lo;
    while (i < mid && j < hi)
        a[k++] = (buf[i] <= buf[j]) ? buf[i++] : buf[j++];
    while (i < mid)
        a[k++] = buf[i++];
}

static void sort_range(int *a, int *buf, size_t lo, size_t hi) {
    if (hi - lo < 2) return;
    size_t mid = lo + (hi - lo) / 2;
    sort_range(a, buf, lo, mid);
    sort_range(a, buf, mid, hi);
    merge(a, buf, lo, mid, hi);
}

/* 0 - успех, -1 - не хватило памяти под буфер */
int merge_sort(int *a, size_t n) {
    if (n < 2) return 0;
    int *buf = malloc(n * sizeof *buf);
    if (buf == NULL) return -1;
    sort_range(a, buf, 0, n);
    free(buf);
    return 0;
}

int main(void) {
    int data[] = {38, 27, 43, 3, 9, 82, 10};
    size_t n = sizeof data / sizeof data[0];
    if (merge_sort(data, n) != 0) {
        fputs("out of memory\n", stderr);
        return 1;
    }
    for (size_t i = 0; i < n; i++)
        printf("%d ", data[i]);
    putchar('\n');
    return 0;
}

cc -std=c11 -Wall -Wextra -o merge_sort merge_sort.c && ./merge_sort

Программа печатает 3 9 10 27 38 43 82. Индексы имеют тип size_t, середина считается как lo + (hi - lo) / 2 — так же, как в Java, чтобы сумма индексов не переполнилась на очень больших массивах.

Сравнение с другими сортировками

Как выбирать по задаче:

• нужна устойчивость и гарантия худшего случая — слияние или библиотечный Timsort;
• важна память, устойчивость не нужна — пирамидальная сортировка;
• короткие или почти упорядоченные массивы — вставки;
• пузырек и его модификации (шейкерная сортировка, «расческа») — учебные алгоритмы, в рабочем коде их не применяют.

Когда сортировку слиянием выбирают на практике

• Стандартные библиотеки. sorted() и list.sort() в Python используют Timsort — гибрид слияния и вставок. В Java Arrays.sort для массивов объектов и Collections.sort устойчивы и тоже основаны на Timsort, а для массивов примитивов Arrays.sort использует быструю сортировку с двумя опорными элементами (устойчивость для примитивов не видна, у них нет «идентичности»).
• Внешняя сортировка. Когда данные не помещаются в оперативную память, их сортируют кусками, пишут на диск и затем сливают отсортированные куски за последовательные проходы. Так устроены сортировки больших файлов и часть операций сортировки в СУБД.
• Связные списки. Слияние списков не требует буфера — достаточно переставлять ссылки, а произвольный доступ по индексу, нужный быстрой сортировке, у списка дорогой.
• Подсчет инверсий. Во время слияния, когда элемент правой половины обгоняет левые, число оставшихся левых элементов — это число пар «стоят не по порядку». Так за O(n log n) считают, насколько один порядок отличается от другого.

Выводы

• Сортировка слиянием делит массив пополам, сортирует половины рекурсивно и сливает их двумя указателями.
• Сложность O(n log n) гарантирована на любом входе; цена — буфер O(n) в классической версии для массивов.
• Устойчивость держится на одном символе: при равенстве брать элемент из левой половины (<=), и проверять ее нужно тестом на повторяющихся ключах.
• В рабочем коде обычно берут встроенную сортировку языка; собственная реализация нужна для обучения, внешней сортировки, списков и задач вроде подсчета инверсий.

Где применяется / связь с практикой

FAQ

Можно ли написать сортировку слиянием без рекурсии?
Да, это восходящий вариант (bottom-up): сначала сливают пары соседних элементов, затем пары блоков по 2, по 4 и так далее, пока блок не станет размером с весь массив. Сложность та же, но нет стека рекурсии.

Почему не делить массив на три части вместо двух?
Так можно, но число уровней падает лишь с log2(n) до log3(n), а каждое слияние трех частей требует больше сравнений на элемент. Асимптотика остается O(n log n), а реализация усложняется, поэтому классикой остается деление пополам.

Сортировка слиянием быстрее быстрой сортировки?
Не обязательно. У слияния лучше гарантия худшего случая, но хорошо реализованная быстрая сортировка на массивах в памяти часто быстрее на практике за счет работы на месте и лучшей локальности кеша. Сравнивать нужно замером на своих данных.