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

Сортировка слиянием является процессом объединения двух или

более упорядоченных наборов данных в один упорядоченный набор

данных. В процессе сортировки поочередно сравниваются ключи в парах

записей из исходных наборов данных так, что записи с меньшими

ключами помещаются в результирующий набор данных. После того как

один набор данных окажется исчерпанным, все оставшиеся элементы

другого пересылаются в результирующий набор без изменения порядка

следования.

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

C(N+M) двух упорядоченных массивов A(N) и B(M) имеет вид.

Пример 1. На примере (заставка с пересылкой из А в С оставшихся).

Характеристики метода.

1. Количество просмотров - не более Log2 N.

2. Число операций сравнения зависит от количества записей

наиболее короткого исходного набора, а также от конкретных

значений ключей элементов исходных массивов.

3. Требуется дополнительная память для хранения вспомогатель-

ного набора данных, в котором могут храниться объединенные файлы.

Данный метод можно использовать для сортировки одного набора данных. Для этого набор данных разделяется на N частей размером в один

элемент, и объединяются соседние (необъединенные) пары элементов.

В результате образуются примерно N/2 частей размером в два эле-

мента. Этот процесс продолжается, пока не останется только одна

последовательность размером N.

Ниже показано, как выполняется этот процесс на последова-

тельности примера. Каждая отдельная часть на рисунке заключена в

скобки.

Исходный файл: [25] [57] [48] [37] [12] [92] [86] [33]

Просмотр 1 [25 57] [37 48] [12 92] [33 86]

Просмотр 2 [25 37 48 57] [12 33 86 92]

Просмотр 3 [12 25 33 37 48 57 86 92]