Внешняя сортировка - часть 3
Порождает ли этот выбор с замещением длинные отрезки? Ясно, что он делает это, по крайней мере, не хуже, чем очевидный метод, так как все отрезки (кроме, возможно, последнего) содержат не меньше
имен. На самом деле можно показать, что средняя длина отрезков, порождаемых выбором с замещением, равна
, и это вполне можно считать улучшением по сравнению с очевидным методом, в котором средняя длина отрезков равна
. Конечно, в лучшем случае все заканчивается только одним исходным отрезком, то есть отсортированной таблицей.
После того, как порождены исходные отрезки, возникает задача повторного распределения их по рабочим лентам и слияния их вместе до тех пор, пока в конце концов мы не получим окончательную отсортированную таблицу. Простейший метод состоит в том, чтобы распределить отрезки по лентам
равномерно и произвести их слияние на ленту
. Получаемые в результате отрезки снова равномерно распределить по лентам
и снова произвести слияние, образуя более длинные отрезки на ленте
. Процесс продолжается до тех пор, пока на ленте
не останется только один отрезок (отсортированная таблица).
Содержание Назад Вперед