Кури внешнюю сортировку. Хорошо описана у того-же Кнута.
Не понял, что имелось в виду под записи типа "short"
Если сами записи большие, а сортировка идёт по небольшому ключу, то можно делать в два прохода:
Первый - собираем по файлу все ключи и их сортируем в памяти как обычно.
Второй - перемещаем записи на свои места.
Товарищь имел ввиду, что файл оооочень большой и в физическую память его не считать, а технологиями типа mmap (проэцирует файл в память) он пользоваться по чему-то не хочет. Ну в такой ситуации мне видиться только самостоятельная эмуляция этго процесса (mmap), через обычные функции чтения/записи файлов, но быстрее оно точно работать небудет.
