Структура данных и алгоритмов

Допустим, в нашем распоряжении к сегментов памяти; к > 1. Заполняем их данными, считывая начало файла или разделяемой части файла и начинаем — в памяти — разделение на «большие» и «меньшие» записи. Для накопления «меньших» используем 1-й сегмент, для «больших» — все остальные. Дело в том, что мы пока у того «берега», где надо группировать «меньшие».
Дождавшись, когда в 1-м сегменте останутся одни «меньшие» записи, мы разгружаем его в файл, а из файла передаем в сегмент следующую порцию записей и т. д. Тем временем идет вытеснение «меньших» записей из прочих сегментов, т. е. в них остаются «большие». «Паром» приготовлен к перемещению этих записей на другой «берег»: переходим к концу файла (части файла). Если файл большой, штанга с головками совершает большой ход.
Один сегмент, например 1-й, должен быть свободен, иначе не «разгрузить паром»: сначала освобождаем окончание файла или части файла, передавая его записи в 1-й сегмент. Теперь, сегмент за сегментом, переписываем «большие» записи в файл, параллельно заполняя сегменты новыми записями.
Снова начинаем разделение — в пространстве к сегментов — на «большие» и «меньшие» записи, но теперь лишь один сегмент нужен для накопления «больших» (потому что сразу передаем их в файл и берем в него из файла следующую порцию записей), а все прочие постепенно заполняются «меньшими», чтобы быть отправленными «на другой берег», где в файле ранее образовалось свободное место для их размещения. Итак, произойдет 2-й большой ход штанги.
Подобные вышерассмотренным акты сортировки и перемещений записей выполняются вновь и вновь, пока все «меньшие» и все «большие» записи не будут сгруппированы и найдена точка раздела между группами.
Перейдем к оценке метода ПАРОМСОРТ. Влияние ходов штанги на время сортировки можно свести к минимуму. Например, если при разделении на 2 части файла размером 64 Мбайт воспользоваться шестью сегментами памяти по 64 Кбайт каждый, то при случайном наборе значений ключей ходов не будет слишком много: пока готовятся к «отправке» 5 сегментов «больших» записей, примерно столько же выявляется и «меньших», т. е. нерассмотренная часть файла сокращается примерно на 10 сегментов. То же происходит и на другом конце файла, следовательно, ходов окажется около сотни, а средняя их длина определяется размером половины файла (она немного меньше). Нетрудно записать коротенькую программу, выполняющую эти ходы, и убедиться, что они займут считаные секунды. В процессе дальнейшего разделения частей общая длина ходов будет примерно такой же, т. е. время лишь удвоится. Поэтому на первый план выступает задержка обращения к данным на диске, которую мы уменьшаем, считывая с диска большие порции данных.
Рекомендация освобождать память перед сортировкой на диске. Помимо высокого быстродействия достоинством метода является работа в пределах пространства, занятого файлом, т. е. метод предельно компактен.
Под структурами данных будем понимать набор из одного или нескольких имен (с одной стороны) и множества данных (с другой стороны), к которым эти имена позволяют получить доступ. Всякая структура данных может описываться на 3-х различных уровнях, перечисляемых от более абстрактного к более конкретному.
I уровень. Функциональная спецификация, указывающая для некоторого класса имен операции, разрешенные с этими именами, и свойства этих операций. На этом уровне речь идет о внешнем определении, независимо от машины и языка программирования. Программист должен ответить на вопросы: какие операции хотел бы я уметь выполнять над моими данными и каковы свойства этих операций?
II уровень. Логическое описание, которое задает декомпозицию объектов, отвечающую функциональному определению, на более элементарные объекты и декомпозицию соответствующих операций на более элементарные операции. Здесь программист отвечает на вопросы: какие данные известных типов и какие отношения, построенные для этих данных, позволяют удовлетворить функциональной спецификации?
III уровень. Физическое представление, которое дает метод расположения в памяти вычислительной машины тех величин, которые составляют структуру, и отношений между ними, а также способ кодирования операций в языке программирования. Программист здесь решает, как можно изобразить и использовать все это в его конкретной машине, в том конкретном языке программирования, которым он располагает.