Merge Sort Средний ~28 мин чтения

Merge Sort

Урок 4 из 10 в курсе Алгоритмы. Старт.

Interactive

Merge Sort Visualizer

Введите числа и управляйте пошаговым выполнением алгоритма.

sorting

История шагов

Merge Sort

Merge Sort — алгоритм "разделяй и властвуй", который делит массив пополам и затем сливает части.

Основная идея

Рекурсивно делим массив до подмассивов длины 1 и объединяем их в отсортированном порядке.

Пошаговый пример

Исходный массив:

[8, 3, 6, 2, 5, 1]
  1. Делим массив на [8,3,6] и [2,5,1]
  2. Сортируем части рекурсивно: [3,6,8] и [1,2,5]
  3. Сливаем две отсортированные части → [1,2,3,5,6,8]

Псевдокод

function merge_sort(arr):
    if size(arr) <= 1: return arr
    mid = size(arr) / 2
    left = merge_sort(arr[0...mid])
    right = merge_sort(arr[mid...end])
    return merge(left, right)

Оптимизация: Подходит для внешней сортировки и больших объёмов данных на диске.

Сложность

Время O(n log n) во всех случаях.
Память O(n), требуется дополнительная память на слияние.

Когда используется

  • Большие объёмы данных
  • Стабильная сортировка
  • Внешняя сортировка файлов

Ключевые свойства

  • Стабильный
  • Не in-place
  • Хорошая асимптотика