Многопутевое слияние и выбор с замещением

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

Техника выбора с замещением может использоваться на первой фазе внешней сортировки. В этом случае Р выбирается достаточно большим. Каждая запись при выводе замещается очередной записью из исходных данных. Если у новой записи ключ меньше, чем у только что выведенной, то она помечается как не участвующая в дальнейшем выборе, а значение Р уменьшается на единицу и процесс продолжается.

Пример. Пусть исходная последовательность ключей:
2 7 12 3 8 9 4 1 5 11 10 6 и Р=4

Процесс вывода начальных сортированных отрезков иллюстрируется таблицей:

В скобки заключены ключи, не участвующие в дальнейшем выборе. Таким путем удается получить упорядоченные последовательности длиннее Р, что важно, так как время внешней сортировки слиянием в значительной мере зависит от числа начальных отрезков. Э.Ф.Мур предложил изящный способ доказательства того, что средняя длина порождаемого отрезка равна 2Р, проведя аналогию со снегоочисти­телем, движущимся по кругу. Пусть на кольцевую дорогу непре­рыв­но падают снежинки (записи). Снежинки исчезают из системы (запи­си выводятся), когда они сбрасываются за пределы дороги. Точки дороги обозначаются вещественными числами x (0 £ x £1). Снежинка, падающая в точку х, соответствует входной записи с ключом х, а снегоочиститель имитирует процесс вывода. В установившемся режиме общее число снежинок на дороге в точности равно Р. Каждый раз, когда снегоочиститель проходит точку 0, заканчивается формирование нового отрезка. На рис.40 изображено поперечное сечение дороги, когда система находится в

Рис. 39 Аналогия со снегоочистителем

Из рисунка видно, что количество снега, удаляемого за один оборот, вдвое превосходит количество снега, присутствующего на дороге в любой момент.