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

Сначала деление, затем слияние

В начальном примере десять значений. Первое деление даёт две части по пять элементов; следующие части могут иметь разную длину. Один элемент уже отсортирован. Когда обе дочерние части отсортированы, их можно объединить.

Диапазоны записаны как [start, end): левая граница включается, правая — нет. Рамки обозначают [start, middle) и [middle, end). Глубина ноль соответствует всему массиву. Плеер показывает один активный диапазон, а не полное дерево рекурсии.

Почему буфер остаётся отсортированным

Перед слиянием обе части основного ряда отсортированы. Указатели i и j обозначают первые ещё не использованные элементы, k — следующую позицию буфера. Меньший кандидат копируется в буфер, и сдвигается только указатель его исходной части.

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

Равные значения сохраняют порядок

Буквы a и b различают элементы, равные в исходном массиве. При равенстве кандидатов алгоритм выбирает левый: в коде используется <=. Элементы левой части изначально стояли раньше элементов правой, поэтому это правило сохраняет их относительный порядок при каждом слиянии.

Попробуйте 2, 2, 1, 2. В результате три двойки должны идти как 2a, 2b, 2c. Выбор правого кандидата при равенстве нарушил бы стабильность, хотя числовой результат оставался бы отсортированным.

Время, память и счётчики

При n ≥ 2 эта реализация работает за Θ(n log n) в лучшем, среднем и худшем случаях. На каждом уровне рекурсии копируется Θ(n) элементов, а уровней Θ(log n). Уже отсортированный вход тоже проходит через буфер: пропуска упорядоченных слияний в этой версии нет.

Переиспользуемый буфер требует O(n) дополнительной памяти, стек рекурсии — O(log n). Обёртка также копирует вход за O(n) времени и памяти, чтобы не изменять исходный массив. Итоговая дополнительная память — O(n). Для пустого и одиночного входа сравнений и записей слияния нет.

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

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

Эта версия сортирует конечные числа по возрастанию и возвращает новый массив. Деление, выбор при равенстве и порядок копирования через буфер совпадают с плеером; события анимации и снимки здесь опущены.

function mergeSort(values) {
    const result = [...values];
    const buffer = new Array(result.length);
    function sort(start, end) {
        if (end - start <= 1) return;
        const middle = start + Math.floor((end - start) / 2);
        sort(start, middle);
        sort(middle, end);
        let left = start;
        let right = middle;
        for (let k = start; k < end; k++) {
            if (right === end ||
                (left < middle && result[left] <= result[right])) {
                buffer[k] = result[left++];
            } else {
                buffer[k] = result[right++];
            }
        }
        for (let k = start; k < end; k++) result[k] = buffer[k];
    }
    sort(0, result.length);
    return result;
}

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

Слияние гарантирует Θ(n log n) в худшем случае, но требует буфер. Представленные здесь вставки, пузырьковая сортировка и выбор имеют Θ(n²) в худшем случае и O(1) дополнительной памяти при сортировке на месте. Их обёртки с копированием входа дополнительно используют O(n) памяти.

Вставки и пузырьковая сортировка с ранним выходом обрабатывают отсортированный вход за Θ(n); эта сортировка слиянием всё равно требует Θ(n log n). Выбор работает за Θ(n²) при любом порядке входа и делает не более n − 1 обменов. Вставки, пузырьковая сортировка и выбранная реализация слияния стабильны; выбор с дальними обменами — нет.

Что попробовать в плеере

Сравните возрастающий и убывающий массивы одинаковой длины. Деление и число записей слияния совпадут, но число сравнений может отличаться. Затем введите повторяющиеся значения и следите за порядком букв. Одиночное значение и пустой ввод показывают базовый случай.

Визуализация использует API сцены и воспроизведения AlgiViz. Два ряда и события слияния реализованы на этом сайте.

Видеоразбор