Внешняя сортировка.

Внешняя сортировка – это сортировка данных находящихся на внешних носителях. Применяется в тех случаях, когда загрузить все данные в ОЗУ не представляется возможным. Внешняя сортировка должна учитывать особенности внешних накопителей, как правило это более быстрая последовательность чтения по сравнению с произвольным. Иногда может отличаться даже в десятки раз. Внешняя сортировка как правило использует метод слияния.
Основная идея метода:
1 3 9 15 20
2 5 9 9 21
После слияния получаем 1 2 3 5 9 9 9 15 20 21

Простое двупутевое слияние
Начальная подготовка. Заводим 4 файла на четырех различных носителях: два объявляем входными и два выходными. Готовим входные файлы. Резервируем ОЗУ по максимуму. Пусть в памяти помещается К записей. Загружаем из входного файла К записей и сортируем любым методом внутренней сортировки. Выводим отсортированный массив во входной файл 1. Снова читаем очередные К записей из общих данных. Сортируем и выводим во второй входной. Операции повторяем записывая отсортированные фрагменты то в первый то во второй входные файлы, пока исходные данные не исчерпаются.
В результате такой подготовки мы получим в двух входных файлах по несколько упорядоченных цепочек длинной К , кроме последнего длина которого может быть меньше.
Слияние. Берем первые фрагменты из двух входных файлов и выполняем слияние этих двух фрагментов, записываем результат в первый выходной файл. Если один из фрагментов закончился раньше другого, то оставшиеся элементы второго просто переписываем в выходной файл. Когда закончились оба фрагменты, проверяем выше описанные операции для следующих двух, только записываем во второй выходной файл и так далее попеременно выводя в первый и второй выходные файлы.
В результате фазы слияния мы получили в двух выходных файлах те же данные, что и во входных, но длина цепочек в два раза больше, а количество в два раза меньше. Меняем местами входные и выходные файлы. Выходные очищаем и повторяем снова фазу слияния. Повторяем смену файлов до тех пор, пока не получим один упорядоченный файл.

Естественное двупутевое слияние
Недостатком предыдущего метода можно считать необходимость учитывать длину цепочки, что в некоторых случаях не желательно.
Для того что бы не считать длину цепочки можно ввести условие окончания цепочки, таким условием может быть когда следующий элемент меньше предыдущего для возрастающей сортировки. Может так получиться, что первый элемент больше последнего элемента предыдущего фрагмента. В этом случае считаем, что это одна возрастающая цепочка, так как это только ускорит сортировку.