Определение. Целочисленный массив с расположенными по неубыванию или по невозрастанию значениями элементов называется упорядоченным.

Использование упорядоченности позволяет создавать эффективные алгоритмы для решения многих интересных задач.

Задача слияния двух входных упорядоченных массивов А и В состоит в формировании упорядоченного выходного массива С, содержащего все элементы из входных массивов.

Рассмотрим алгоритм слияния для упорядоченных по неубыванию массивов. Вначале элемент А[1] сравнивается с элементом В[1] и наименьший из них записывается в массив С. Если наименьшим был А[1], то на следующем шаге сравниваются А[2] и B[1], а если наименьшим был B[1], то будут сравниваться A[1] и B[2] и т.д. Если на очередном шаге окажется, что из одного входного массива все элементы переписаны в С, то переписывается элемент из другого массива.

Рассмотрим пример работы алгоритма слияния.

Пусть в массиве А содержатся 3 элемента: {5, 13, 14}, а в массиве В - 4 элемента: {7, 9, 10, 12}. Внимательно рассмотрите таблицу, в которой по шагам показано изменение переменных i, i1, i2 и действия с массивами.

Рассмотрите фрагмент решения задачи на слияние двух массивов А и В, которые содержат соответственно n1 и n2 элементов. Результирующий массив С будет содержать n1+n2 элементов.

Задача. Составьте программу, реализующую рассмотренный метод. Дополните ее комментариями.

Рекурсивная сортировка слиянием (для любопытных)

Задача. Напишите программу, содержащую алгоритм слияния в процедуре Sort(A, B, b1, e1, e2). Алгоритм должен копировать со слиянием два упорядоченные куска из массива А с номерами от b1 до e1 и от e1+1 до e2 соответственно в массив В с номерами элементов от b1 до e2.

Предположив, что Вы правильно выполнили предыдущую задачу, алгоритм сортировки можно определить очень просто:

1. если длина сортируемого массива 1, то ничего не делается;



2. в противном случае массив делится на две одинаковые (или почти одинаковые) части, к каждой части применяется алгоритм сортировки, после чего эти упорядоченные части сливаются в один упорядоченный кусок.

Рассмотрите процедуру сортировки слиянием. На вход процедуры сортировки поступает неупорядоченный кусок массива А с номерами элементов от b до e, на выходе - тот же кусок, но упорядоченный. Массив С - вспомогательный.