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

Описание

Сортировка слиянием — алгоритм сортировки. Он был пред­ло­жен Джо­ном фон Ней­ма­ном в 1945 го­ду.

Это устойчивый ал­го­ритм, использующий [math]O(n)[/math] дополнительной памяти и [math]O(n[/math] [math]\log(n))[/math] времени.

• Анимированная работа алгоритма (англ.)

Принцип работы

Пример работы процедуры слияния.

Алгоритм использует прицип «разделяй и властвуй»: задача разбивается на подзадачи меньшего размера, которые решаются по отдельности, после чего их решения комбинируются для получения решения исходной задачи. Конкретно процедуру сортировки слиянием можно описать следующим образом:

1. Если в рассматриваемом массиве один элемент, то он уже отсортирован — алгоритм завершает работу.
2. Иначе массив разбивается на две части, которые сортируются рекурсивно.
3. После сортировки двух частей массива к ним применяется процедура слияния, которая по двум отсортированным частям получает исходный отсортированный массив.

Слияние двух массивов

У нас есть два массива [math]A[/math] и [math]B[/math] (фактически это будут две части одного массива, но для удобства будем писать, что у нас просто два массива). Нам надо получить массив [math]C[/math] размером [math]|A| + |B|[/math]. Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.

Ниже приведён псевдокод процедуры слияния, который сливает две части массива A — [left; mid) и [mid; right)

Merge(A, left, mid, right):
  it1 = 0
  it2 = 0
  result = new int[right - left]
  
  while left + it1 < mid and mid + it2 < right:
    if A[left + it1] < A[mid + it2]:
      result[it1 + it2] = A[left + it1]
      it1 += 1
    else:
      result[it1 + it2] = A[mid + it2]
      it2 += 1
  
  while left + it1 < mid:
    result[it1 + it2] = A[left + it1]
    it1 += 1
  
  while mid + it2 < right:
    result[it1 + it2] = A[mid + it2]
    it2 += 1
  
  for i = 0 to it1 + it2:
    A[left + i] = result[i]

Рекурсивный алгоритм

Пример работы рекурсивного алгоритма сортировки слиянием

Функция сортирует подотрезок массива с индексами в полуинтервале [left; right).

MergeSort(A, left, right):
  if left + 1 >= right:
    return
  mid = (left + right) / 2
  MergeSort(A, left, mid)
  MergeSort(A, mid, right)
  Merge(A, left, mid, right)

Пример работы алгоритма показан на рисунке:

Время работы

Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай [math]T(n)[/math] — время сортировки массива длины n, тогда для сортировки слиянием справедливо [math]T(n)=2T(n/2)+O(n)[/math]
([math]O(n)[/math] — это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:

[math]T(n)[/math] [math]=[/math] [math]2T(n/2)[/math] [math]+[/math] [math]O(n)[/math] [math]=[/math] [math]4T(n/4)[/math] [math]+[/math] [math]2O(n)[/math] [math]=[/math] [math]...[/math] [math]=[/math] [math]2^kT(1)[/math] [math]+[/math] [math]kO(n).[/math]

Осталось оценить [math]k[/math]. Мы знаем, что [math]2^k=n[/math], а значит [math]k=\log n[/math]. Уравнение примет вид [math]T(n)=nT(1)+ \log n[/math] [math]O(n)[/math]. Так как [math]T(1)[/math] — константа, то [math]T(n)=O(n)+\log n [/math] [math]O(n)=O(n\log n)[/math].

Ссылки

• Википедия — сортировка слиянием
• Сортировка слиянием, анимация и свойства (англ.)
• Примеры реализации на различных языках (Википедия)
• Сортировка слиянием в картинках (источник картинок в статье)
• Реализация сортировки слиянием на языке Python