Стр. 96 - Основы алгоритмов и структур данных

94 Содержание
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
06 12* 42 67*.
Соединяем упорядоченные последовательности длинны 2, получаем
06 12 44 94’ 18 42 55 67’.
Третье разделение и слияние приводят нас к желаемому результату
06 12 18 42 44 55 67 94.
Операция, которая однократно обрабатывает все множество данных,
называется фазой, а наименьший подпроцесс, который, повторяясь, образует
процесс сортировки, называется проходом или этапом. В приведенном выше
примере сортировка производится за три прохода, каждый проход состоит из
фазы разбиения и фазы слияния.
с
a
b
с
a
b
с
a
b
с
Фаза слияния
Фаза распределения
с
проход 1 проход 2 проход n
Рис. 73. Фазы сортировки и слияния
Фазы разбиения не относятся к сортировке, поскольку они никак не
переставляют элементы; в каком-то смысле они непродуктивны, хотя и
составляют половину всех операций переписи. Их можно удалить, объединив
фазы разбиения и слияния. Вместо того чтобы сливать элементы в одну
последовательность, результат слияния сразу распределяют в два файла,
которые на следующем проходе будут входными. В отличие от двухфазного
слияния этот метод называется однофазным или сбалансированным слиянием.
Оно имеет явные преимущества, так как требует вдвое меньше операций
переписи.
Теперь перейдём к более детальному рассмотрению программы слияние.
Данные будем представлять в виде массива, обращение к которому происходит
строго последовательно.