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

TL;DR

Сортировка слиянием (merge sort) — рекурсивный алгоритм класса «разделяй и властвуй»: массив делится пополам, половины сортируются рекурсивно, затем сливаются в один отсортированный массив за линейное время. Главные свойства: гарантированное [math]\displaystyle{ O(n\log n) }[/math] в худшем случае (в отличие от quicksort) и устойчивость (при слиянии из двух равных берётся левый). Рекуррентность [math]\displaystyle{ T(n) = 2T(n/2) + \Theta(n) }[/math] решается деревом рекурсии или master theorem (случай 2) → [math]\displaystyle{ \Theta(n\log n) }[/math]. Цена — дополнительная память [math]\displaystyle{ O(n) }[/math] под буфер слияния (на связных списках — [math]\displaystyle{ O(\log n) }[/math] под рекурсию). Итеративная (bottom-up) версия обходится без рекурсии, а слияние как строительный блок используется во внешней сортировке на дисках, сортировке списков, Timsort (план) и при подсчёте инверсий за [math]\displaystyle{ O(n\log n) }[/math].

Свойство	Значение
Класс	Сортировка сравнением; «разделяй и властвуй»
Автор	Джон фон Нейман (John von Neumann), 1945
Лучший случай	[math]\displaystyle{ O(n\log n) }[/math]
Средний случай	[math]\displaystyle{ O(n\log n) }[/math]
Худший случай	[math]\displaystyle{ O(n\log n) }[/math]
Память	[math]\displaystyle{ O(n) }[/math] дополнительно (списки — [math]\displaystyle{ O(\log n) }[/math] под рекурсию)
Устойчивость	да
Локальность	хорошая (последовательные проходы)
Ключевые части	деление пополам, устойчивое слияние, (bottom-up) — пары отрезков
Родственники	Timsort (план), Быстрая сортировка, Пирамидальная сортировка
Где встречается	внешняя сортировка, списки, `std::stable_sort`, MapReduce

Определения

Сортировка слиянием (merge sort) — алгоритм сортировки массива [math]\displaystyle{ a[lo..hi) }[/math]:

Разделить отрезок пополам в позиции mid;
Отсортировать рекурсивно [math]\displaystyle{ a[lo..mid) }[/math] и [math]\displaystyle{ a[mid..hi) }[/math];
Слить две отсортированные половины в один отсортированный отрезок.

Слияние (merge) — объединение двух отсортированных последовательностей в одну отсортированную за [math]\displaystyle{ O(len_1 + len_2) }[/math] с помощью двух указателей.

Устойчивость (stability). Равные элементы сохраняют исходный порядок. Сортировка слиянием устойчива, если при равных элементах слияние берёт элемент из левой половины (см. рис. 3).

Рекуррентность. [math]\displaystyle{ T(n) = 2T(n/2) + \Theta(n) }[/math], [math]\displaystyle{ T(1) = \Theta(1) }[/math]; отсюда [math]\displaystyle{ T(n) = \Theta(n\log n) }[/math].

Bottom-up (итеративная) версия — без рекурсии: сливаем соседние отрезки удваивающейся ширины [math]\displaystyle{ 1, 2, 4, \dots }[/math] (см. рис. 4).

Естественная (natural) сортировка слиянием — сначала находит уже упорядоченные серии (runs) и сливает их; это предок Timsort (план).

Инверсия — пара индексов [math]\displaystyle{ i \lt j }[/math], где [math]\displaystyle{ a[i] \gt a[j] }[/math]. Число инверсий — мера «беспорядка»; сортировка слиянием считает их за [math]\displaystyle{ O(n\log n) }[/math] (см. рис. 5).

Обозначения. [math]\displaystyle{ n }[/math] — длина массива; [math]\displaystyle{ lo, mid, hi }[/math] — границы; [math]\displaystyle{ \log }[/math] — двоичный; под «слиянием» понимается устойчивое слияние.

Общая схема «разделяй и властвуй» показана на рис. 1.

Рис. 1. Схема «разделяй и властвуй»: деление пополам, рекурсивная сортировка половин, слияние за [math]\displaystyle{ \Theta(n) }[/math].

Мотивация и интуиция

Нужен алгоритм с гарантией [math]\displaystyle{ O(n\log n) }[/math] и устойчивостью, чего нет у Быстрая сортировка (худший [math]\displaystyle{ \Theta(n^2) }[/math], неустойчива) и Пирамидальная сортировка (неустойчива, плохая локальность). Сортировка слиянием даёт оба свойства: деление всегда пополам (нет «плохих» входов), а слияние из двух равных берёт левый (устойчивость).

Идея в одном абзаце: сортировать половины и слить их дешевле, чем сортировать целиком. Если обе половины отсортированы, объединение в один отсортированный массив линейно. Дерево рекурсии всегда сбалансировано: глубина ровно [math]\displaystyle{ \lceil\log_2 n\rceil }[/math], на каждом уровне суммарно [math]\displaystyle{ n }[/math] работы слияний, итого [math]\displaystyle{ \Theta(n\log n) }[/math] — см. рис. 2. Плата — дополнительный буфер, равный сливаемому отрезку (обычно [math]\displaystyle{ O(n) }[/math]).

Рис. 2. Дерево рекурсии: [math]\displaystyle{ \log n }[/math] уровней по [math]\displaystyle{ \Theta(n) }[/math] работы — гарантия [math]\displaystyle{ \Theta(n\log n) }[/math] при любом входе.

Устройство

Сердце алгоритма — слияние. Пока в обеих половинах есть элементы, сравниваем их «фронты» и выпускаем меньший: строго меньший правый — берём правый, иначе левый (при равенстве — левый, что и даёт устойчивость). См. рис. 3.

Рис. 3. Слияние [1,2,5,8] и [3,4,7,9]: два указателя; при равенстве берётся левый элемент.

Рекурсивная схема хранит буфер для слияния; чтобы не выделять память на каждом уровне, его создают один раз (или чередуют два массива). Bottom-up-версия обходится и без рекурсии.

Операции и алгоритмы

Операция: слияние (Merge)

Идея. Два указателя идут по отсортированным половинам; каждый раз выбирается меньший элемент.

Пошаговое описание:

i ← lo, j ← mid, k ← lo.
Пока i < mid и j < hi: если a[j] < a[i], скопировать a[j] в буфер и увеличить j, иначе скопировать a[i] и увеличить i.
Дописать остатки (левый или правый).
Скопировать буфер обратно в a[lo..hi).

Инвариант. В буфере buf[lo..k-1] — отсортированные первые k - lo элементов объединения; a[i..mid) и a[j..hi) — нетронутые остатки.

Процедура Merge(a, lo, mid, hi, buf)
Вход:  a[lo..mid) и a[mid..hi) отсортированы; buf — буфер
Выход: a[lo..hi) отсортирован
Инвариант: buf[lo..k−1] — отсортированное объединение взятых частей
Сложность: Θ(hi − lo)
Корректность: после дописывания остатков buf[lo..hi) — отсортированное объединение половин

1  i ← lo ; j ← mid ; k ← lo
2  while i < mid and j < hi
3      if a[j] < a[i]           # строго меньше → берём правое
4          buf[k] ← a[j] ; j ← j + 1
5      else                     # иначе левое (устойчиво при равенстве)
6          buf[k] ← a[i] ; i ← i + 1
7      k ← k + 1
8  while i < mid: buf[k] ← a[i] ; i ← i + 1 ; k ← k + 1
9  while j < hi:  buf[k] ← a[j] ; j ← j + 1 ; k ← k + 1
10 for t ← lo to hi − 1: a[t] ← buf[t]

Разбор. [1,2,5,8] и [3,4,7,9]: выпускаем 1,2,3,4,5,7,8,9 (рис. 3).

Крайние случаи. Один из отрезков пуст — слияние сводится к копированию другого. Равные элементы — берём левый.

Операция: MergeSort (top-down)

Идея. Отсортировать половины рекурсивно и слить их. Деление всегда пополам, поэтому дерево рекурсии сбалансировано при любом входе.

Пошаговое описание:

Если hi − lo ≤ 1, отрезок уже отсортирован — выйти (база рекурсии).
Вычислить mid ← lo + ⌊(hi − lo) / 2⌋.
Рекурсивно отсортировать a[lo..mid).
Рекурсивно отсортировать a[mid..hi).
Слить половины процедурой Merge(a, lo, mid, hi, buf).

Инвариант. На входе вызова a[lo..hi) — перестановка исходных элементов этого отрезка; после возврата a[lo..hi) отсортирован, элементы вне отрезка не изменяются.

Алгоритм MergeSort(a, lo, hi, buf)
Вход:  массив a; границы 0 ≤ lo < hi ≤ n; buf — буфер длины n
Выход: a[lo..hi) отсортирован
Инвариант: a[lo..hi) — перестановка исходных элементов отрезка
Сложность: T(n) = 2·T(n/2) + Θ(n) = Θ(n log n); стек O(log n)

1  if hi − lo ≤ 1: return
2  mid ← lo + ⌊(hi − lo) / 2⌋
3  MergeSort(a, lo, mid, buf)
4  MergeSort(a, mid, hi, buf)
5  Merge(a, lo, mid, hi, buf)

Корректность: индукция по длине отрезка. База hi − lo ≤ 1 очевидна; шаг — половины
отсортированы по предположению индукции, а Merge по лемме даёт отсортированный a[lo..hi).

Разбор. [5,2,8,1,9,3,7,4] → половины [5,2,8,1], [9,3,7,4] → … → слияние даёт [1,2,3,4,5,7,8,9] (рис. 1).

Сложность. [math]\displaystyle{ \Theta(n\log n) }[/math] во всех случаях — см. рекуррентность; память: буфер [math]\displaystyle{ O(n) }[/math] (один на все вызовы) плюс стек рекурсии [math]\displaystyle{ O(\log n) }[/math].

Крайние случаи. [math]\displaystyle{ n \le 1 }[/math] — немедленный возврат (пустой и одноэлементный массивы). Все элементы равны — дерево то же, [math]\displaystyle{ \Theta(n\log n) }[/math], порядок равных сохраняется. Буфер выделяется один раз на все вызовы: если заводить его в каждом вызове, память вырастает до [math]\displaystyle{ O(n\log n) }[/math].

Операция: Bottom-up MergeSort

Идея. Без рекурсии: сливать соседние отрезки ширины [math]\displaystyle{ 1, 2, 4, \dots }[/math], пока ширина не станет не меньше [math]\displaystyle{ n }[/math].

Пошаговое описание:

Установить width ← 1.
Пройти массив блоками длины 2·width, начиная с lo ← 0.
Для блока вычислить mid ← min(lo + width, n) и hi ← min(lo + 2·width, n).
Если mid < hi, слить a[lo..mid) и a[mid..hi); иначе блок один — пропустить.
Удвоить ширину (width ← width · 2) и повторять, пока width < n.

Инвариант. После завершения прохода ширины w каждый блок длины 2w (кроме, возможно, последнего, обрезанного границей массива) отсортирован.

Алгоритм MergeSort-BottomUp(a, buf)
Вход:  массив a[0..n); buf — буфер длины n
Выход: a отсортирован
Инвариант: после прохода ширины w каждый блок длины 2w отсортирован
Сложность: Θ(n log n); рекурсии нет, стек O(1)

1  n ← length[a]
2  width ← 1
3  while width < n
4      lo ← 0
5      while lo < n
6          mid ← min(lo + width, n)
7          hi  ← min(lo + 2·width, n)
8          if mid < hi
9              Merge(a, lo, mid, hi, buf)
10         lo ← lo + 2·width
11     width ← width · 2

Корректность: индукция по ширине. При width = 1 каждый блок отсортирован; проход удваивает
длину отсортированного блока, пока один блок не покроет весь массив.

Разбор. [5,2,8,1,9,3,7,4]: ширина 1 → [2,5][1,8][3,9][4,7]; ширина 2 → [1,2,5,8][3,4,7,9]; ширина 4 → [1,2,3,4,5,7,8,9] (рис. 4).

Сложность. [math]\displaystyle{ \lceil\log_2 n\rceil }[/math] проходов по [math]\displaystyle{ \Theta(n) }[/math]; [math]\displaystyle{ O(1) }[/math] дополнительного стека.

Крайние случаи. Последний отрезок может быть короче — границы обрезаются через min. Для [math]\displaystyle{ n \le 1 }[/math] внешний цикл не выполняется ни разу; при нечётном [math]\displaystyle{ n }[/math] последний блок на каждом проходе сливается с более коротким соседом либо остаётся как есть.

Рис. 4. Bottom-up: слияние отрезков ширины 1, 2, 4, … без рекурсии.

Операция: подсчёт инверсий

Идея. При слиянии, если берём элемент из правой половины, все ещё не взятые левые элементы больше него (левая отсортирована) — это mid − i новых инверсий (см. рис. 5).

Функция Count-Inversions(a, lo, hi, buf)
Вход:  массив a[lo..hi); buf — буфер длины n
Выход: число инверсий в a[lo..hi)
Инвариант: buf[lo..k−1] — слитый префикс; inv — инверсии внутри половин
           и найденные перекрёстные инверсии
Сложность: Θ(n log n); память O(n)

1  if hi − lo ≤ 1: return 0
2  mid ← lo + ⌊(hi − lo) / 2⌋
3  inv ← Count-Inversions(a, lo, mid, buf) + Count-Inversions(a, mid, hi, buf)
4  i ← lo ; j ← mid ; k ← lo
5  while i < mid and j < hi
6      if a[j] < a[i]
7          inv ← inv + (mid − i)
8          buf[k] ← a[j] ; j ← j + 1
9      else
10         buf[k] ← a[i] ; i ← i + 1
11     k ← k + 1
12 while i < mid: buf[k] ← a[i] ; i ← i + 1 ; k ← k + 1
13 while j < hi:  buf[k] ← a[j] ; j ← j + 1 ; k ← k + 1
14 for t ← lo to hi − 1: a[t] ← buf[t]
15 return inv

Корректность: инверсии делятся на три группы — обе половины (рекурсия) и перекрёстные
(левая половина, правая половина); последние считаются пачками mid − i при взятии a[j].

Разбор. [3,6,7,9 | 1,2,5]: левая половина [3,6,7,9], правая [1,2,5], указатель i стоит на 3.

Взяли 1: 1 < 3, поэтому все ещё не взятые левые элементы (3,6,7,9) образуют с 1 инверсии — mid − i = 4; i не сдвигается.
Взяли 2: 2 < 3, снова +4.
Дальше 3 < 5 — берём 3 из левой половины, инверсий нет, i сдвигается на 6; теперь 5 < 6 — +3 (6,7,9 против 5).
Итого 4 + 4 + 3 = 11 (рис. 5).

Крайние случаи. Уже отсортированный массив — 0 инверсий; обратный порядок — [math]\displaystyle{ n(n-1)/2 }[/math].

Рис. 5. Подсчёт инверсий [3,6,7,9 | 1,2,5]: при взятии 1 — +4, при 2 — +4, при 5 — +3; всего 11.

Сводная таблица сложности

Операция	Время	Память
`Merge`	[math]\displaystyle{ \Theta(len_1 + len_2) }[/math]	[math]\displaystyle{ O(1) }[/math] сверх буфера
`MergeSort` (top-down)	[math]\displaystyle{ \Theta(n\log n) }[/math]	[math]\displaystyle{ O(n) }[/math] буфер + [math]\displaystyle{ O(\log n) }[/math] стек
`MergeSort` (bottom-up)	[math]\displaystyle{ \Theta(n\log n) }[/math]	[math]\displaystyle{ O(n) }[/math] буфер, стек [math]\displaystyle{ O(1) }[/math]
Сортировка списка	[math]\displaystyle{ \Theta(n\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math] (слияние указателей)
Подсчёт инверсий	[math]\displaystyle{ \Theta(n\log n) }[/math]	[math]\displaystyle{ O(n) }[/math]

Оговорка: все оценки — гарантированные (лучший, средний и худший совпадают по классу [math]\displaystyle{ \Theta(n\log n) }[/math]); в отличие от quicksort, «плохих» входов нет. Память [math]\displaystyle{ O(n) }[/math] — основной недостаток на больших массивах в RAM.

Трассировка примера

a = [5, 2, 8, 1, 9, 3, 7, 4].

Уровень	Отрезки	После слияния
старт	`[5][2][8][1][9][3][7][4]`	—
1	пары по 1	`[2,5] [1,8] [3,9] [4,7]`
2	пары по 2	`[1,2,5,8] [3,4,7,9]`
3	по 4	`[1,2,3,4,5,7,8,9]`

Слияние [2,5] и [1,8]: 1 (из прав.), 2 (лев.), 5 (лев.), 8 (прав.) → [1,2,5,8]; устойчивость: равные элементы сохраняют исходный порядок. Трассировка сверена с реализацией из раздела «Служебное».

Корректность и оценка сложности

Корректность слияния

Утверждение. Если [math]\displaystyle{ a[lo..mid) }[/math] и [math]\displaystyle{ a[mid..hi) }[/math] отсортированы, то Merge делает [math]\displaystyle{ a[lo..hi) }[/math] отсортированным.

Доказательство. Инвариант: buf[lo..k-1] — отсортированное объединение уже взятых частей, и каждый элемент буфера не больше любого ещё не взятого (так как указатели идут по возрастанию и выбирается меньший из фронтов). По завершении взяты все элементы, буфер отсортирован. [math]\displaystyle{ \square }[/math]

Устойчивость. При равенстве a[i] = a[j] условие a[j] < a[i] ложно, поэтому берётся левый элемент — порядок равных сохраняется.

Корректность сортировки

Индукция по длине. База: [math]\displaystyle{ n \le 1 }[/math] отсортирован. Шаг: по индукции половины отсортированы; слияние даёт отсортированный отрезок (лемма выше). [math]\displaystyle{ \square }[/math]

Оценка времени

Дерево рекурсии: на уровне [math]\displaystyle{ i }[/math] — не более [math]\displaystyle{ 2^i }[/math] узлов, а суммарный размер узлов уровня не превосходит [math]\displaystyle{ n }[/math] (каждый элемент входит не более чем в один узел), поэтому работа уровня — [math]\displaystyle{ O(n) }[/math]. Уровней [math]\displaystyle{ \lceil\log_2 n\rceil + 1 }[/math], поэтому [math]\displaystyle{ T(n) = \Theta(n\log n) }[/math]. Формально — master theorem, случай 2: [math]\displaystyle{ a = 2 }[/math], [math]\displaystyle{ b = 2 }[/math], [math]\displaystyle{ n^{\log_b a} = n = f(n) \Rightarrow \Theta(n\log n) }[/math] (см. Асимптотическая сложность (план)).

Оценка памяти

Массив: буфер на один отрезок — [math]\displaystyle{ O(n) }[/math]; стек рекурсии — [math]\displaystyle{ O(\log n) }[/math]. Связный список: слияние переставляет указатели, дополнительная память — только стек [math]\displaystyle{ O(\log n) }[/math]. Внешняя сортировка: память ограничена размером блока, а не всем объёмом данных.

Сравнение с альтернативами

Алгоритм	Средний	Худший	Память	Устойчив	Локальность
Слиянием	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n) }[/math]	да	хорошая
Быстрая	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n^2) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	нет	отличная
Пирамидальная	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]	нет	плохая
Timsort (план)	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n) }[/math]	да	хорошая, адаптивна
Introsort	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	нет	отличная

Рис. 6. Сортировка слиянием против quicksort, heapsort, Timsort и introsort: гарантия и устойчивость ценой [math]\displaystyle{ O(n) }[/math] памяти.

Вердикт. Нужна устойчивость, гарантия или внешняя/списочная сортировка — берём слияние (или Timsort (план), если важна адаптивность); сводка различий — см. рис. 6. Нужна максимальная скорость в RAM и допустима неустойчивость — Быстрая сортировка. Нужна [math]\displaystyle{ O(1) }[/math] памяти — Пирамидальная сортировка.

Где применяется

Ниже — пять мест, где выбирают слияние (обзор — см. рис. 7); в каждом пункте объяснено, почему выбрано именно это решение.

Внешняя сортировка (диски). Данные не влезают в память: сортируем блоки в RAM, затем многократно сливаем отсортированные потоки ([math]\displaystyle{ k }[/math]-way merge) — классическая схема внешней сортировки. Почему: слияние читает/пишет последовательно, минимизируя обращения к диску [2][6].

Связные списки. Сортировка слиянием на списке не требует произвольного доступа и переставляет только указатели; например, std::list::sort в C++ и Collections.sort для списков в Java. Почему: слияние естественно работает с указателями за [math]\displaystyle{ O(\log n) }[/math] памяти [3][4].

Устойчивая сортировка. std::stable_sort (C++), Timsort (Python/Java) и другие устойчивые сортировки основаны на слиянии. Почему: устойчивость задаётся слиянием «из двух равных берём левый» [1][4].

Подсчёт инверсий. Мера «беспорядка» массива и минимальное число соседних обменов до сортировки считаются сортировкой слиянием за [math]\displaystyle{ O(n\log n) }[/math] вместо наивного [math]\displaystyle{ O(n^2) }[/math]. Почему: при слиянии инверсии считаются пачками [1][5].

Сортировка в БД и распределённых системах. Sort-merge join в СУБД и фаза sort в MapReduce строятся на слиянии отсортированных потоков. Почему: слияние — линейная, устойчивая, поэтапно распараллеливаемая операция [6].

Рис. 7. Где применяется слияние: внешняя сортировка, списки, устойчивые сортировки, инверсии, join и MapReduce.

Историческая справка

Сортировка слиянием восходит к Джону фон Нейману (John von Neumann): метод описан в его отчёте по проекту EDVAC (1945) и в работе с Германом Голдстайном (1948). Её считают одним из первых алгоритмов сортировки, для которых была выведена оценка [math]\displaystyle{ O(n\log n) }[/math] ⚠️ требует проверки точной атрибуции. Метод изложен в классических учебниках: Кнут, The Art of Computer Programming, т. 3 (сортировка, в том числе внешняя — balanced multiway merge) [2], и CLRS, гл. 2 (mergesort; задача 2-4 о подсчёте инверсий) [1].

Итеративную (bottom-up) схему и приёмы внешней сортировки систематизировали в 1960–1970-е годы (Кнут, а также работы по внешней сортировке на магнитных лентах) ⚠️ требует проверки. Идея использовать уже упорядоченные серии развилась в natural merge sort, а затем — в Timsort (план) Тима Петерса (2002), где слияние с политикой на стеке и галопированием доведено до стандарта Python/Java [4].

Типичные ошибки и подводные камни

Неустойчивое слияние. Если при равенстве брать правый элемент (a[j] <= a[i]), сортировка перестаёт быть устойчивой; нужно строгое <.
Лишняя память. Выделять буфер на каждом вызове — расточительно; заводите один буфер (или чередуйте два массива).
Ошибки в границах. Использовать полуоткрытые интервалы [math]\displaystyle{ [lo, hi) }[/math] и следить за mid — иначе дублируются или теряются элементы.
Переполнение (lo+hi)/2. Пишите lo + (hi - lo)/2.
Глубина рекурсии. [math]\displaystyle{ O(\log n) }[/math] безопасно, но на очень больших данных иногда переходят на bottom-up.
Сортировка малых массивов. На маленьких [math]\displaystyle{ n }[/math] слияние проигрывает вставкам; гибриды переключаются на сортировку вставками при [math]\displaystyle{ n \lt 16/32 }[/math].
Дописывание остатка. Забыть скопировать остаток одной из половин — классическая ошибка; инвариант требует дописать оба остатка.
Слияние без проверки порядка. Merge предполагает отсортированные половины; вызов без рекурсии сломает результат.
Списки vs массивы. На массиве нужен буфер; на списке — нет, но слияние идёт по указателям.
Инверсии и переполнение. Число инверсий до [math]\displaystyle{ n(n-1)/2 }[/math] — при [math]\displaystyle{ n }[/math] порядка [math]\displaystyle{ 10^5 }[/math] нужен long long.

Задачи для практики

Основная реализация. Напишите рекурсивную сортировку слиянием с одним буфером. Подсказка: полуоткрытый интервал [math]\displaystyle{ [lo, hi) }[/math].

Устойчивость. Докажите, что слияние устойчиво, и приведите контрпример для <=. Подсказка: сравнение a[j] < a[i].

Bottom-up. Реализуйте итеративную версию и сравните с рекурсивной по памяти. Подсказка: удвоение ширины.

Инверсии. Посчитайте число инверсий за [math]\displaystyle{ O(n\log n) }[/math] и сверьте с [math]\displaystyle{ O(n^2) }[/math] на малых [math]\displaystyle{ n }[/math]. Подсказка: + (mid − i) при взятии правого.

k-way merge. Слейте [math]\displaystyle{ k }[/math] отсортированных массивов за [math]\displaystyle{ O(N\log k) }[/math] (куча минимумов). Подсказка: очередь с приоритетом на головах.

Списки. Отсортируйте односвязный список слиянием без буфера; оцените память. Подсказка: слияние по указателям.

Внешняя сортировка. Схема «блоки + многопроходное слияние»: сколько проходов при памяти [math]\displaystyle{ M }[/math] и данных [math]\displaystyle{ N }[/math]? Подсказка: каждый проход уменьшает число потоков.

Естественные серии. Найдите отсортированные runs и слейте их; сравните с обычным слиянием на почти отсортированных данных. Подсказка: предок Timsort.

Ответы и оценки сложности.

[math]\displaystyle{ T(n) = 2T(n/2) + \Theta(n) = \Theta(n\log n) }[/math]; память [math]\displaystyle{ O(n) }[/math] (буфер) + [math]\displaystyle{ O(\log n) }[/math] (стек).
При a[i] = a[j] условие a[j] < a[i] ложно, поэтому берётся левый; контрпример для <= — пары с равными ключами (1,a), (1,b): правый уйдёт первым, порядок нарушится.
Время то же [math]\displaystyle{ \Theta(n\log n) }[/math]; выигрыш только в памяти под стек: [math]\displaystyle{ O(1) }[/math] вместо [math]\displaystyle{ O(\log n) }[/math].
Для [3,6,7,9,1,2,5] ответ 11; сложность [math]\displaystyle{ \Theta(n\log n) }[/math], память [math]\displaystyle{ O(n) }[/math].
[math]\displaystyle{ O(N\log k) }[/math] времени ([math]\displaystyle{ N }[/math] — суммарная длина), [math]\displaystyle{ O(k) }[/math] памяти на кучу; наивный повторный выбор минимума даёт [math]\displaystyle{ O(Nk) }[/math].
[math]\displaystyle{ \Theta(n\log n) }[/math] времени, [math]\displaystyle{ O(\log n) }[/math] памяти под рекурсию; буфер не нужен.
Начальных серий [math]\displaystyle{ \lceil N/M \rceil }[/math]; при [math]\displaystyle{ k }[/math]-путевом слиянии проходов [math]\displaystyle{ \lceil \log_k \lceil N/M \rceil \rceil }[/math], объём ввода-вывода [math]\displaystyle{ \Theta(N \log_k \lceil N/M \rceil) }[/math].
На почти отсортированных данных серий мало: время [math]\displaystyle{ \Theta(n\log r) }[/math], где [math]\displaystyle{ r }[/math] — число серий, то есть близко к [math]\displaystyle{ \Theta(n) }[/math] вместо [math]\displaystyle{ \Theta(n\log n) }[/math] в общем случае — это и есть идея, доведённая до Timsort.

Связанные темы

Быстрая сортировка — быстрее в среднем, но неустойчива и без гарантии.
Пирамидальная сортировка — гарантия при [math]\displaystyle{ O(1) }[/math] памяти.
Timsort — адаптивная устойчивая сортировка на основе слияния.
Сортировки — обзор алгоритмов и нижняя граница [math]\displaystyle{ \Omega(n\log n) }[/math].
Асимптотическая сложность — рекуррентности и master theorem.

Источники

Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 2 «Getting Started» (mergesort); задача 2-4 о подсчёте инверсий; §4.4 (дерево рекурсии).
Knuth D. E. The Art of Computer Programming. Vol. 3: Sorting and Searching. — Addison-Wesley, 2nd ed., 1998. — §5.2.4 (сортировка слиянием), §5.4 (внешняя сортировка).
Sedgewick R., Wayne K. Algorithms. 4th ed. — Addison-Wesley, 2011. — Гл. 2.2 (mergesort), приложения к сортировке списков.
Peters T. listsort.txt (Timsort как эволюция natural mergesort). URL: https://github.com/python/cpython/blob/main/Objects/listsort.txt.
Wikipedia: Merge sort. URL: https://en.wikipedia.org/wiki/Merge_sort.
Silberschatz A., Korth H. F., Sudarshan S. Database System Concepts. — McGraw-Hill, 7th ed., 2019 (sort-merge join, внешняя сортировка).

Поиск

Навигация

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

Содержание

TL;DR

Определения

Мотивация и интуиция

Устройство

Операции и алгоритмы

Операция: слияние (Merge)

Операция: MergeSort (top-down)

Операция: Bottom-up MergeSort

Операция: подсчёт инверсий

Сводная таблица сложности

Трассировка примера

Корректность и оценка сложности

Корректность слияния

Корректность сортировки

Оценка времени

Оценка памяти

Сравнение с альтернативами

Где применяется

Историческая справка

Типичные ошибки и подводные камни

Задачи для практики

Связанные темы

Источники