Как работает алгоритм внешней сортировки?

Алгоритм внешней сортировки предназначен для работы с большими объёмами данных, которые не помещаются в оперативную память. en.wikipedia.org intuit.ru

В основе большинства методов внешних сортировок лежит процедура слияния и распределения: intuit.ru

• Слияние — объединение двух (или более) упорядоченных серий в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент. intuit.ru
• Распределение — разделение упорядоченных серий на два и более вспомогательных файла. intuit.ru

Общий алгоритм сортировки слиянием: intuit.ru

1. Серии распределяются на два или более вспомогательных файлов. intuit.ru Распределение идёт поочерёдно: первая серия записывается в первый вспомогательный файл, вторая — во второй и так далее до последнего вспомогательного файла. intuit.ru Затем опять запись серии начинается в первый вспомогательный файл. intuit.ru
2. После распределения всех серий, они объединяются в более длинные упорядоченные отрезки. intuit.ru Из каждого вспомогательного файла берётся по одной серии, которые сливаются. intuit.ru Если в каком-то файле серия заканчивается, то переход к следующей серии не осуществляется. intuit.ru
3. В зависимости от вида сортировки сформированная более длинная упорядоченная серия записывается либо в исходный файл, либо в один из вспомогательных файлов. intuit.ru
4. После того как все серии из всех вспомогательных файлов объединены в новые серии, потом опять начинается их распределение. intuit.ru И так до тех пор, пока все данные не будут отсортированы. intuit.ru

Внешняя сортировка применяется, например, для сортировки таблиц по определённому столбцу. habr.com