re:re:actable
Урок 042 минуты чтения

Что такое 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.

Документация

Wikipedia: Merge sort.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам