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

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

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

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

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

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

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

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

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

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

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

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

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

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

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