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

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

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

Сортировка слиянием — вероятно, один из самых простых алгоритмов сортиров­ки (среди «быстрых» алгоритмов).Сортировка слиянием — стабильный алгоритм сортировки. Это означает, что по­рядок «равных» элементов не изменяется в результате работы алгоритма. В не­которых задачах это свойство достаточно важно. Этот алгоритм был предложен Джоном фон Нейманом в 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(nlog(n))[/math].