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

Новое разбиение пополам и слияние упорядоченных пар дает последовательность

Слияние в упорядоченные пары дает последовательность

Об, 67

Об, 67

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

Первый шаг: разбиение дает две последовательности

44, 94, 18, 55', Об, 12', 42, 67

Об, 12, 44, 94', 18, 42, 55, 67

Об, 12, 18, 42, 44, 55, 67, 94

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

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

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

Рис. 3.22. Схема сортировки прямым слиянием для двух файлов

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

а = (int*)malloc( 2* п* sizeoj{ini)); . Пусть l,j — фиксируют два исходных элемента; к, I — два выходных. Исходные данные — это элементы а\, ...,а_п. Для указания направления пересылки введем логическую переменную up. Если ир = 1, то в текущем проходе компоненты cii,...,a_n движутся на место а_п+\,..., а_2гъ если же ир = 0, то а_п+\,..., а_1п пересылаются в a_t,..., a_n. Между последовательными проходами значение up изменяется на противоположное. Пусть р — длина сливаемых последовательностей. Начальное значение р равно 1, и перед каждым последующим проходом она удваивается. Для простоты мы предполагаем, что всегда п равно степени двойки.