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

Идея

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

1. Разделяй — делим массив на две половины.
2. Властвуй — рекурсивно сортируем каждую половину (массив из одного элемента уже отсортирован).
3. Объединяй — сливаем две отсортированные половины: раз за разом берём меньший из двух первых элементов.

Слияние двух отсортированных списков общей длины n требует всего n − 1 сравнений — в этом весь секрет.

Пример

Сортируем [5, 2, 4, 6, 1, 3]:

                [5, 2, 4, 6, 1, 3]
               /                  \
        [5, 2, 4]                [6, 1, 3]
         /     \                  /     \
     [5, 2]    [4]            [6, 1]    [3]
     /    \                   /    \
   [5]    [2]               [6]    [1]
     \    /                   \    /
     [2, 5]    [4]            [1, 6]    [3]
         \     /                  \     /
        [2, 4, 5]                [1, 3, 6]
               \                  /
                [1, 2, 3, 4, 5, 6]

Последнее слияние по шагам — сравниваем первые элементы и берём меньший:

Левая	Правая	Берём	Результат
2, 4, 5	1, 3, 6	1	1
2, 4, 5	3, 6	2	1, 2
4, 5	3, 6	3	1, 2, 3
4, 5	6	4	1, 2, 3, 4
5	6	5	1, 2, 3, 4, 5
—	6	6	1, 2, 3, 4, 5, 6

Попробуйте сами

Тот же пример по шагам. Измените данные или нажмите «Старт».

Псевдокод

MERGE-SORT(A, low, high)
  if low ≥ high
    return
  mid = ⌊(low + high) / 2⌋
  MERGE-SORT(A, low, mid)
  MERGE-SORT(A, mid + 1, high)
  if A[mid] ≤ A[mid + 1]              // половины уже по порядку
    return
  MERGE(A, low, mid, high)

MERGE(A, low, mid, high)
  copy A[low..high] to B[low..high]
  i = low, j = mid + 1
  for k = low to high
    if i > mid:            A[k] = B[j], j = j + 1
    else if j > high:      A[k] = B[i], i = i + 1
    else if B[j] < B[i]:   A[k] = B[j], j = j + 1
    else:                  A[k] = B[i], i = i + 1   // при равенстве берём левый: устойчиво

Сложность

Лучший	Средний	Худший	Память	Устойчивая	На месте
O(n)	O(n log n)	O(n log n)	O(n)	да	нет

• Рекуррентное соотношение $T(n)=2T(n/2)+\mathrm{\Theta }(n)$ даёт $T(n)=\mathrm{\Theta }(n\log n)$: в дереве рекурсии ${\log }_{2}n$ уровней, и на каждом уровне суммарно сливается n элементов.
• Проверка A[mid] ≤ A[mid + 1] пропускает слияние уже упорядоченных половин, поэтому отсортированный массив обрабатывается за O(n).
• Память O(n) на буфер — один буфер выделяется один раз и переиспользуется.
• Устойчивая: при равенстве слияние сначала берёт элемент из левой половины.

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

Когда нужна устойчивая сортировка или гарантированные O(n log n). Она же лежит в основе внешней сортировки (данные не помещаются в память) и TimSort — алгоритма Array.prototype.sort.

Использование

import { mergeSort } from 'ts-ds';

const tasks = [
  { title: 'B', priority: 2 },
  { title: 'A', priority: 1 },
  { title: 'C', priority: 2 },
];
mergeSort(tasks, (a, b) => a.priority - b.priority);
// A (1), B (2), C (2) — B остаётся перед C

Справочник API

Литература

• Кормен, §2.3 «Разработка алгоритмов» (слияние и «разделяй и властвуй»), глава 4 (рекуррентные соотношения).
• Седжвик, Алгоритмы, §2.2 «Сортировка слиянием».
• Кнут, Искусство программирования, т. 3, §5.2.4 «Сортировка слиянием».