Внешняя сортировка - часть 3

Порождает ли этот выбор с замещением длинные отрезки? Ясно, что он делает это, по крайней мере, не хуже, чем очевидный метод, так как все отрезки (кроме, возможно, последнего) содержат не меньше

$m$

имен. На самом деле можно показать, что средняя длина отрезков, порождаемых выбором с замещением, равна

$2m$

, и это вполне можно считать улучшением по сравнению с очевидным методом, в котором средняя длина отрезков равна

$m$

. Конечно, в лучшем случае все заканчивается только одним исходным отрезком, то есть отсортированной таблицей.

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

$1,2,\ldots,t$

равномерно и произвести их слияние на ленту

$t + 1$

. Получаемые в результате отрезки снова равномерно распределить по лентам

$1,2,\ldots,t$

и снова произвести слияние, образуя более длинные отрезки на ленте

$t + 1$

. Процесс продолжается до тех пор, пока на ленте

$t + 1$

не останется только один отрезок (отсортированная таблица).

Содержание Назад Вперед