Изменения

[[Файл:Merge-sort1.gif|right|380px|thumb|Действие алгоритма.]]

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

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

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

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

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

[[Файл:Mergearr.png|right|300px|thumb|Пример работы процедуры слияния.]]

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

Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <tex>T(n)</tex> - время сортировки массива длины n, тогда для сортировки слиянием справедливо <tex>T(n)=2T(n/2)+O(n)</tex> <br>

(<tex>O(n)</tex> - это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:

*[http://ru.wikipedia.org/wiki/Mergesort Википедия - сортировка слиянием]

*[http://iproc.ru/parallel-programming/lection-6/ Сортировка слиянием]