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

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

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

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

Рассмотрим алгоритм слияния для упорядоченных по неубыванию массивов. Вначале элемент А[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 элементов.