logo search
Сборная ответов к госэкзаменам

Ускорение сортировки слиянием

Мы продемонстрировали пример процедуры сортировки слиянием, которая начи­нается с серий длины 1. Мы сэкономили бы немало времени, если бы начали эту процедуру с прохода, который считывает в основную память группы из k записей (при соответствующем k), сортирует их (например, с помощью процедуры быстрой сортировки) и записывает во внешнюю память в виде серии длиной k.

Если, например, у нас есть миллион записей, нам потребуется 20 проходов по этим данным, чтобы выполнить сортировку, начиная с серий длиной 1. Если, одна­ко, у нас есть возможность одновременно поместить в основную память 10 000 запи­сей, то мы сможем за один проход прочитать 100 групп из 10 000 записей, отсорти­ровать каждую группу и получить таким образом 100 серий длиной 10 000, поделен­ных поровну между двумя файлами. Таким образом, всего семь проходов и слияний потребовалось бы для сортировки файла, содержащего не более 10 000 х 27 = 1 280 000 записей.