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

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

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

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

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

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

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

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

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

2. Раз­бить имею­щие­ся от­сор­ти­ро­ван­ные це­поч­ки на па­ры, и осу­ще­ствить слия­ние це­по­чек каж­дой па­ры.

3. Ес­ли чис­ло от­сор­ти­ро­ван­ных це­по­чек боль­ше еди­ни­цы, пе­рей­ти к ша­гу 2.

Слияние 2-х массивов

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

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

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

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

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

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

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

// r и l - правая и левая граница массива, m - середина
	m  =  r  /  2   // делим на 2 половины
	if  m  ==  r    // условие выхода - если массив стал состоять из 1 элемента
	    return
	sort  a[l..m]   // рекурсивная сортировка правой и левой частей, в функцию передаются левая и правая границы массива
	sort  a[m+1..r]
	merge  (a[l..m], a[m+1..r]) // делаем процедуру слияния 2х отсортированных половинок

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

Время работы

Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай [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].

Свойства

Стабильный.

[math]O(n)[/math] дополнительной памяти для массива.

[math]O(lg(n))[/math] дополнительной памяти для связных списков.

[math]O(n[/math] [math]lg(n))[/math] времени.

Ссылки

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