Я не выискивал текущее определение двухпроходной сортировки с множественным слиянием, но теория «внешней сортировки» (где данные слишком велики, чтобы поместиться в памяти) в значительной степени стандартна. Любая приличная книга по алгоритмам покроет это; среди многих других вы можете взглянуть на Кнута, Седжвика или (для археологов программного обеспечения) Kernighan & Plauger Software Tools .
Основная техника проста:
- Чтение данных до тех пор, пока не останется свободного места.
- Сортируй.
- Запись во временный файл.
- Повторяйте от 1 до тех пор, пока не останется данных для чтения.
- Вы знаете, сколько у вас временных файлов, N.
- Вам нужно определить, сколько из этих файлов вы можете прочитать одновременно, M.
- Если N> M, то вы проектируете фазу слияния так, чтобы последняя фаза объединяла M-файлы.
- Вы объединяете наборы M файлов в новые временные файлы, пока не достигнете последнего слияния.
- Вы объединяете последний набор M файлов (или N, если N
Все ужасно стандартно - но есть мелкие детали, чтобы получить право.
В томе II системы AT & T по чтению систем Unix была хорошая статья под названием «Теория и практика построения процедуры рабочей сортировки», которую вы должны найти и прочитать, если вы серьезно относитесь к изучению обработки внешних сортировок. Однако, когда вы читаете его, помните, что машины сильно изменились с момента его написания, с гигабайтами основной памяти (вместо мегабайт) и терабайтами дискового пространства (или SSD - также вместо мегабайт).