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

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

Действие алгоритма на примере сортировки случайных точек.

Сортировка слиянием — Сор­ти­ров­ка слия­ни­ем — ве­ро­ят­но, один из са­мых про­стых ал­го­рит­мов сор­ти­ров­ки (сре­ди «быст­рых» ал­го­рит­мов). Осо­бен­но­стью это­го ал­го­рит­ма яв­ля­ет­ся то, что он ра­бо­та­ет с эле­мен­та­ми мас­си­ва пре­иму­ще­ствен­но по­сле­до­ва­тель­но, бла­го­да­ря че­му имен­но этот ал­го­ритм ис­поль­зу­ет­ся при сор­ти­ров­ке в си­сте­мах с раз­лич­ны­ми ап­па­рат­ны­ми огра­ни­че­ни­я­ми.

Кро­ме то­го, сор­ти­ров­ка слия­ни­ем — чуть ли не един­ствен­ный ал­го­ритм, ко­то­рый мо­жет быть эф­фек­тив­но ис­поль­зо­ван для сор­ти­ров­ки та­ких ст­рук­тур дан­ных, как свя­зан­ные спис­ки. По­сле­до­ва­тель­ная ра­бо­та с эле­мен­та­ми мас­си­ва зна­чи­тель­но уве­ли­чи­ва­ет ско­рость сор­ти­ров­ки в си­сте­мах с кэ­ши­ро­ва­ни­ем.

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

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

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

Для решения задачи сортировки эти три этапа выглядят так:

• Сортируемый массив разбивается на две части примерно одинакового размера;
• Каждая из получившихся частей сортируется отдельно, обычно - рекурсивно, тем же самым алгоритмом;
• Два упорядоченных массива половинного размера соединяются в один.

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

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

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

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

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

a = 0; b = 0;
While (a < [math]n_a[/math]) and (b < [math]n_b[/math])  
  If A[a] [math]\leqslant[/math] B[b]
    C[a + b] = A[a];
    a = a + 1;
  Else
    C[a + b] = B[b];
    b = b + 1;
  End;
End;
If a < [math]n_a[/math]
  Copy remain part of A
Else
  Copy remain part of B
End;

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

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

Function MergeSort(a,b)
  If b = a then Exit;
  c = (a + b)/2;
  Mergesort(a,c);
  MergeSort(c + 1,b);
  Merge fragments (a,c) and (c + 1,b);
End

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

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

Время работы

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

T(n) = 2T(n/2) + O(n) = 4T(n/4) + 2*O(n) = ... = 2^kT(1) + kO(n). 

Осталось оценить [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].

Ссылки

• Википедия - сортировка слиянием
• Сортировка слиянием