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

Описание

Действие алгоритма.

Сортировка слиянием — алгоритм сортировки, хороший пример использования принципа «разделяй и властвуй». Он был пред­ло­жен Джо­ном фон Ней­ма­ном в 1945 го­ду.

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

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

Принцип «разделяй и властвуй» — сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Про­це­ду­ра слия­ния тре­бу­ет два от­сор­ти­ро­ван­ных мас­си­ва. За­ме­тив, что мас­сив из од­но­го эле­мен­та по опре­де­ле­нию яв­ля­ет­ся от­сор­ти­ро­ван­ным, мы мо­жем осу­ще­ствить сор­ти­ров­ку сле­дую­щим об­ра­зом:

1. Раз­бить имею­щие­ся эле­мен­ты мас­си­ва на па­ры и осу­ще­ствить слия­ние эле­мен­тов каж­дой па­ры, по­лу­чив от­сор­ти­ро­ван­ные це­поч­ки дли­ны 2 (кро­ме, быть мо­жет, од­но­го эле­мен­та, для ко­то­ро­го не на­шлось па­ры).
2. Раз­бить имею­щие­ся от­сор­ти­ро­ван­ные це­поч­ки на па­ры, и осу­ще­ствить слия­ние це­по­чек каж­дой па­ры.
3. Ес­ли чис­ло от­сор­ти­ро­ван­ных це­по­чек боль­ше еди­ни­цы, пе­рей­ти к ша­гу 2.

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

Допустим, у нас есть два отсортированных массива А и B размерами [math]N_a [/math] и [math]N_b [/math] со­ответственно, и мы хотим объединить их элементы в один большой отсортирован­ный массив C размером [math]N_a + N_b [/math] . Для этого можно применить процедуру слия­ния, суть которой заключается в повторяющемся «отделении» элемента, наи­меньшего из двух имеющихся в началах исходных массивов, и присоединении это­го элемента к концу результирующего массива. Элементы мы переносим до тех пор, пока один из исходных массивов не закончится. После этого оставшийся «хвост» одного из входных массивов дописывается в конец результирующего мас­сива. Пример работы процедуры показан на рисунке:

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

Алгоритм слияния формально можно записать следующим образом:

// слияние двух массивов с помощью временного
merge(array a, int left, int middle, int right) // left - левая граница, right - правая, middle - середина
  array b = a[middle + 1, right];
  i = left, j = middle + 1, k = 0;
  array temp;
  while i <= middle and j <= right
    temp[k++] = (a[j] < b[i]) ? a[j++] : b[i++];
  while i <= middle
    temp[k++] = b[i++];
  while j <= right
    temp[k++] = a[j++];
  for (int t = 0; t != k; t++)
    a[t] = temp[t]
// в конце a[1..k] это будет отсортированный массив

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

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

Проще всего формализовать этот алгоритм рекурсивным способом. Функция сортирует участок массива от элемента с номером left до элемен­та с номером right:

sort(array a, int left, int right) // right и left — правая и левая граница массива, middle — середина
  middle = right / 2  
  if middle == right    // условие выхода — если массив стал состоять из 1 элемента
    return
  sort(a, left, middle) 
  sort (a, middle + 1, right)
  merge(array a, left, middle, 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]2*O(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)O(n)[/math]. Так как [math]T(1)[/math] — константа, то [math]T(n)=O(n)+\log(n)O(n)=O(n\log(n))[/math].

Ссылки

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