95
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Вместо двух файлов, можно легко использовать один массив, если
рассматривать его как последовательность с двумя концами. Вместо того,
чтобы сливать элементы из двух исходных файлов, мы можем брать их с двух
концов массива. Таким образом, общий вид объединенной фазы слияния-
разбиения можно изобразить, как показано на рис. 74. Направление пересылки
сливаемых элементов меняется (переключается) после каждой упорядоченной
пары на первом проходе, после каждой упорядоченной четверки на втором
проходе и т. д.; таким образом, равномерно заполняются две выходные
последовательности, представленные двумя концами одного массива
(выходного). После каждого прохода два массива меняются ролями: входной
становится выходным, и наоборот.
входной массив
выходной массив
слияние
разбиение
i
j
k
l
Рис. 75. Сортировка двух массивов методом простого слияния
Программу можно еще больше упростить, объединив два концептуально
различных массива в один массив двойной длины.
Пусть индексы
i
и
j
указывают два исходных элемента, тогда как
k
и
l
обозначают два места пересылки (см. рис. 74). Исходные данные — это,
элементы
a
1
,...,
а
n
. Очевидно, что нужна булевская переменная
up
для указания
направления пересылки данных;
up
=
true
будет означать, что на текущем
проходе компоненты
a
1
,...,
а
n
будут пересылаться “вверх” — в переменные
a
n
+1
,...,
а
2
n
, тогда как
up
false
будет указывать, что
a
n
+1
,...,
а
2
n
должны
переписываться “вниз” — в
a
1
,...,
а
n
. Значение
up
строго чередуется между
двумя последовательными проходами. И, наконец, вводится переменная
р
для
обозначения длины сливаемых подпоследовательностей (
р
-наборов). Ее
начальное значение равно 1, и оно удваивается перед каждым очередным
проходом. Для простоты мы будем считать, что
n
— всегда степень двойки.
Таким образом, программа простого слияния имеет вид
1...,87,88,89,90,91,92,93,94,95,96 98,99,100,101,102,103,104,105,106