Метод слияния. Сортировка слиянием, НГТУ, информатика, контрольная

Фрагмент работы:

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

Данный метод был предложен Джоном фон Нейманом в 1945 г. и предназначался для сортировки файлов. Под сортировкой слиянием будем понимать объединение двух (или нескольких) упорядоченных (например, по возрастанию) последовательностей в одну упорядоченную. Это можно сделать следующим образом: сравнить наименьшие элементы из последовательностей и наименьший из них занести в третью конечную последовательность. Этот процесс продолжить до того, как одна из последовательностей закончится, «хвост» оставшейся последовательности записать в третью последовательность. В нашем примере нет необходимости переписывать «хвост» — это предусмотрено условием цикла while.

Рассмотрим пример, реализованный в программе. Даны две последовательности из 9 чисел:

A[n]={1,3,5,7,9,11,13,15,17}

B[n]={2,4,6,8,10,12,14,16,18}

C[2*n] – конечная последовательность

Сравниваем наименьшие элементы:

1 3 5 7 9 11 13 15 17

||

2 4 5 8 10 12 14 16 18

||

1

На втором шаге получим:

1 3 5 7 9 11 13 15 17

||

2 4 5 8 10 12 14 16 18

||

1 2

На третьем шаге:

1 3 5 7 9 11 13 15 17

||

2 4 5 8 10 12 14 16 18

||

1 2 3

Процесс продолжаем до конца последовательностей.

…