йнием. Слияние означает объединение двух (или более) опядоченных последовательностей в одну упорядоченную У^дедовательность при помощи циклического выбора эле- рятов, доступных в данный момент. Слияние - намного бо- простая операция, чем сортировка; она используется рвачестве вспомогательной в более сложном процессе по- ледовательной сортировки. Один из методов сортировки диящ^€М называется простым слиянием и состоит в следующем:

J Последовательность а разбивается на две половины Ь и с. 2 Последовательности бис сливаются при помощи объединения отдельных элементов в упорядоченные пары.

3. Полученной последовательности присваивается имя а, и повторяются шаги 1 и 2; на этот раз упорядоченные пары сливаются в упорядоченные четверки.

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

В качестве примера рассмотрим последовательность

44 55 12 42 94 18 06 67

На первом шаге разбиение дает последовательности

44 55 12 42 94 18 06 67

Слияние отдельных компонент (которые являются упорядоченными последовательностями длины 1) в упорядоченные пары дает

44 94 18 55 06 12 42 67 Новое разбиение пополам и слияние упорядоченных пар дают 06 12 44 94 18 42 55 67

Tpefbe разбиение и слияние приводят, наконец, к нужному результату:

06 12 18 42 44 55 67 94

Операция, которая однократно обрабатывает все множество данных, называется фазой, а наименьший подпроцесс, который, повторяясь, образует процесс сортировки, иазы-зется проходом или этапом. В приведенном выше примере Сортировка производится за три прохода, каждый проход со-сгоит из фазы разбиения и фазы слияния. Для выполнения ортировки требуются три магнитные ленты, поэтому процесс азывается трехленточным слиянием.

Собственно говоря, фазы разбиения не относятся к copjj ровке, поскольку они никак не переставляют элементы; в ка ком-то смысле они непродуктивны, хотя и составляют полц, вину всех операций переписи. Их можно удалить, объедини фазы разбиения и слияния. Вместо того чтобы сливать эд, менты в одну последовательность, результат слияния сразу распределяют на две ленты, которые на следующем проход будут входными. В отличие от двухфазного слияния этот ме,-тод называется однофазным или сбалансированным слия, нием. Оно имеет явные преимущества, так как требует вдво меньще операций переписи, но это достигается ценой исполь. зования четвертой ленты.

входной массив выходной массив

разбиение I

Рис. 2.12. Сортировка двух массивов методом простого слияния.

Разберем программу слияния подробно; предположим сначала, что данные расположены в виде массива, который, однако, можно просматривать только строго последовательно. Другая версия сортировки слиянием будет основана на файловой структуре, это позволит сравнить эти программы и показать строгую зависимость формы программы от представления ее данных. i

Вместо двух файлов можно легко использовать один массив, если рассматривать его как последовательность с двумя концами. Вместо того чтобы сливать элементы из двух исходных файлов, мы можем брать их с двух концов массива. Таким образом, общий вид объединенной фазы слияния-разбиения можно изобразить, как показано на рис. 2.12. Направление пересылки сливаемых элементов няется (переключается) после каждой упорядоченной пары на первом проходе, после каждой упорядоченной четверки втором проходе и т. д.; таким образом равномерно запол; няются две выходные последовательности, представленные двумя концами одного массива (выходного). После каждог прохода два массива меняются ролями: входной становится выходным и наоборот.

Программу можно еще больще упростить, объединив Д^ концептуально различных массива в один массив двойное

дяны- Итак, данные будут представлены следующим об-Р^° а: аггау[1.. 2 * п] of item (2.20)

flvcTb индексы t н / указывают два исходных элемента, тогда как * и обозначают два места пересылки (см. рис. 2.12). Исходные данные - это, разумеется, элементы Ui, Очевидно, что нужна булевская переменная up для указания направления пересылки данных; up = true будет означать что на текущем проходе компоненты ai, а„ будут пересылаться вверх - в переменные On+i, ..., Огл, тогда как Jp = false будет указывать, что an+i, а^п должны переписываться вниз - в аи an. Значение up строго чередуется между двумя последовательными проходами. И наконец, вводится переменная р для обозначения длины сливаемых подпоследовательностей (р-наборов). Ее начальное значение равно 1, и оно удваивается перед каждым очередным проходом. Для простоты мы будем считать, что п - всегда степень двойки. Итак, первая версия программы простого слияния имеет такой вид:

procednre mergesort; var i,j,k,l: index;

up: Boolean; p: integer; begin up :== true; p :~ 1; Repeat {инициация индексов} if up then

begin i 1; J := n; к := n+l; I := 2*и

end else (2.21)

begin := 1; / := ; i := и-Ы;; := 2*n

end;

слияниеj9-wfl6Qpoe последовательностей i иУ в последовательности к и / ; up :== -up; р := 2*р until р п end

На следующем этапе мы уточняем действие, описанное на естественном языке (внутри кавычек). Ясно, что этот проход, Обрабатывающий п элементов, состоит из последовательных лияний р-наборов. После каждого отдельного слияния на-Равление пересылки переключается из нижнего в верхний онец выходного массива или наоборот, чтобы обеспечить Двыаковое распределение в обоих направлениях. Если сли-аемые элементы посылаются в нижний конец массива, то чдексом пересылки служит k v. k увеличивается на 1 после