Что такое merge sort?
На этой странице
Merge sort - сортировка divide and conquer: массив делится пополам, половины сортируются рекурсивно и затем сливаются. Сложность всегда O(n log n), но нужна дополнительная память O(n).
Вопрос
Как работает merge sort и почему его сложность O(n log n)?
Идея
[5, 2, 8, 1]
-> [5, 2] [8, 1]
-> [5] [2] [8] [1]
-> [2, 5] [1, 8]
-> [1, 2, 5, 8]Реализация
function mergeSort(nums: number[]): number[] {
if (nums.length <= 1) return nums
const mid = Math.floor(nums.length / 2)
const left = mergeSort(nums.slice(0, mid))
const right = mergeSort(nums.slice(mid))
return merge(left, right)
}
function merge(left: number[], right: number[]): number[] {
const result: number[] = []
let i = 0
let j = 0
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) result.push(left[i++])
else result.push(right[j++])
}
return result.concat(left.slice(i), right.slice(j))
}Главная работа происходит в merge: две уже отсортированные половины сливаются, как две стопки карт, - каждый раз берем меньшую из верхних.
left = [2, 5], right = [1, 8]
i=0, j=0: 2 vs 1 -> берем 1 result = [1]
i=0, j=1: 2 vs 8 -> берем 2 result = [1, 2]
i=1, j=1: 5 vs 8 -> берем 5 result = [1, 2, 5]
left закончился, дописываем остаток right -> [1, 2, 5, 8]Каждый элемент попадает в результат один раз, поэтому слияние стоит O(n). Условие left[i] <= right[j] (а не <) берет равный элемент из левой половины первым - так сортировка остается стабильной.
Сложность
Time: O(n log n)
Space: O(n)Почему n log n:
log nуровней деления;- на каждом уровне суммарно сливаем
nэлементов.
уровень 0: [8 элементов] слияние: 8 операций
уровень 1: [4] [4] слияние: 4 + 4 = 8
уровень 2: [2] [2] [2] [2] слияние: 8
уровень 3: [1] [1] [1] [1] [1] [1] [1] [1]3 уровня (log2(8) = 3) по 8 операций - всего 8 * 3, то есть n log n.
Что отвечать на собеседовании?
Merge sort делит массив пополам до единичных элементов, затем сливает отсортированные части. Он стабилен и гарантированно работает за O(n log n), но требует O(n) дополнительной памяти. Хорошо демонстрирует divide and conquer.
Что важно помнить: частые ошибки
- Забывать base case.
- Не учитывать память из-за
slice. - Ошибаться в merge-цикле.
- Говорить, что merge sort in-place в обычной реализации.
- Не понимать, откуда берется
log n.
Мини-шпаргалка
- Divide and conquer.
- Split -> sort -> merge.
- Time
O(n log n). - Space
O(n). - Stable.
- Хорош для linked list и external sorting.