Не очень понятно, зачем здесь Z. Если 1000 структур помещается в памяти, и мы их можем отсортировать, то казалось бы - читаем из файла 10 раз по 1000 структур (по порядку, за один проход), каждый раз структуры сортируем и в отсортированном порядке помещаем в новый файл. Всего получается 10 файлов. Дальше - обычный merge. Кстати, слить можно сразу все 10 файлов, если их можно открыть одновременно. Если нет - сливаем два самых маленьких файла, пока не останется один (выгодно, чтобы сливаемые файлы были примерно одинакового размера - как группы символов в коде Хаффмана).
Возможно, Z придумали, чтобы файлы были не совсем одинаковыми, чтобы алгоритм не закладывался на одинаковость размера. Но тогда лучше было бы, например, "случайное число от 500 до 1000". В любом случае, если брать не максимум, то алгоритму только хуже.
Средний
