Сортировка слиянием
Сливаем отсортированные прогоны удваивающейся ширины — всегда O(n log n), без худших случаев.
1function mergeSort(a: number[]): number[] {2 for (let width = 1; width < a.length; width *= 2) {3 for (let start = 0; start < a.length; start += 2 * width) {4 merge(a, start, start + width, Math.min(start + 2 * width, a.length))5 }6 }7 return a8}9 10function merge(a: number[], lo: number, mid: number, hi: number): void {11 const left = a.slice(lo, mid)12 const right = a.slice(mid, hi)13 let i = 0, j = 0, k = lo14 while (i < left.length && j < right.length) {15 a[k++] = left[i] <= right[j] ? left[i++] : right[j++]16 }17 while (i < left.length) a[k++] = left[i++]18 while (j < right.length) a[k++] = right[j++]19}Проблема
Отсортировать массив гарантированно за O(n log n). Быстрая сортировка в худшем случае деградирует до O(n²); слияние — единственный популярный метод с жёсткой гарантией и устойчивостью.
Что вы видите
Столбики. Два соседних отсортированных прогона подсвечены диапазонами; на каждом шаге меньшая «голова» прогонов переезжает на следующую позицию — прогон удваивается.
Как это работает
Восходящая схема: прогоны шириной 1 уже «отсортированы»; слияние двух прогонов даёт ширину 2, затем 4, 8… log₂(n) уровней по n сравнений-перемещений. Слияние бережёт порядок равных (устойчивость), поэтому живёт в Timsort.
Пошаговый разбор
- 01
Прогоны ширины 1
Каждый элемент — готовый прогон.
- 02
Слияние
Две головы; меньшая уходит в результат.
- 03
Удвоение
Ширина прогонов ×2 на каждом уровне.
- 04
Финал
Один прогон на весь массив.
Complexity и ограничения
Устойчивая. Гарантия O(n log n). Требует O(n) дополнительной памяти (буфер слияния).
Edge cases
- Отсортирован
Всё равно n log n/2 сравнений — предсказуемость вместо адаптивности.
- Обратный порядок
Худший случай по сравнениям, но всё ещё n log n.
- Связные списки
Слияние — метод выбора: O(1) памяти.
Где встречается в реальности
Timsort
Python/Java: слияния + вставки — устойчивость обязательна.
Внешняя сортировка
Данные больше памяти сливают с диска прогонами.
MapReduce
Фаза reduce — по сути массовое слияние отсортированных потоков.
Связанные алгоритмы
«Сортировка без худших случаев: слияния»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.