Изменения

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

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

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

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

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

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

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

sort(array a, int left, int right) // right и left — правая и левая граница массива, middle — середина

if middle == right // условие выхода — если массив стал состоять из 1 элемента