Упорядоченность компонент файла по одному или нескольким ключевым полям — одно из основных условий эффективной реализации задач обработки файлов. Так, задача распечатки файла в определенном порядке следования компонент, если файл не упорядочен соответствующим образом, решается с помощью многократных просмотров (прогонов) файла. Количество прогонов при этом пропорционально количеству компонент.
Отсутствие прямого доступа к компонентам приводит к тому, что рассмотренные выше алгоритмы сортировок массива невозможно эффективно адаптировать для сортировки файла. В отличие от массивов, основные критерии эффективности алгоритма сортировки файла — количество прогонов файлов и количество промежуточных файлов.
Так, например, алгоритм сортировки простыми обменами требует N прогонов сортируемого файла (N — количество компонент файла). Алгоритм быстрой сортировки вообще не имеет смысла рассматривать, поскольку при его реализации необходимо было бы читать файл от конца к началу!
Рассмотрим поэтому новый для нас алгоритм — алгоритм сортировки слиянием, который наиболее эффективен при сортировке файлов и относится к быстрым алгоритмам при сортировке массивов, хотя и требует дополнительной памяти.
