Никак не могу понять смысл этой сортировки.

Если кто забыл, смысл в том, чтобы остсортировать файл, используя ещё 3 файла, чтоб разделять "серии" и вроде можно брать из каждого файла только по одному числу для сравнения.

И вот значит есть у меня файлы f1, f2 и g1, g2. Сначала пусть  все числа в файле f1, а f2 - пустой.
Числа пусть такие - 200, 4, 60, 11, 2, 0, 50, 6, 3, 20, 14, 60.
И теперь нужно произвольно разделить эти числа в оба файла: f1: (200, 4, 60, 11, 2, 50), f2:(0, 6, 3, 20, 14, 60), т.е. длина серии пока равна 1.
Затем происходит слияние в серии по 2 и получаются такие файлы:
g1: (0, 200), (3, 60), (2, 14), 
g2: (4, 6) , (11, 20), (50, 60) - Это понятно как получается - из файлов f1 и f2 по очереди выбираются числа, сравниваются и упорядоченными парами записываются поочереди в g1 и g2.

Но вот что происходит дальше? Далее, как везде написано, всё делается аналогично - пары сливаются в четвёрки, четвёрки в восьмёрки и т.д. 
Т.е. взяв последние пары (2, 14) и (50, 60) я должен получить отсортированную четвёрку (2, 14, 50, 60), но как? Ведь я могу доставать числа из файлов g1 и g2 строго последовательно и никаких массивов у меня нет и сортировать я их не могу.
Может я не так понял алгоритм?

Внешняя сортировка используется когда объема ОЗУ не достаточно для размещения всех сортируемых данных, и как следствие "обычные" алгоритмы сортировки не подходят.

В этом случае делают так: 
1) читаем из файла(Ф0) столько данных сколько влезет в ОЗУ, сортируем их "обычным" алгоритмом сортировки.
2) результат сохраняем в промежуточный файл(Ф1).
3) читаем из файла(Ф0) столько данных сколько влезет в ОЗУ, сортируем их "обычным" алгоритмом сортировки.
4) имеем две порции отсортированных данных: одна в файле(Ф1), одна в ОЗУ
5) объединяем обе порции и сохраняем их в файл(Ф2)
6) удаляем файл Ф1
7) переименовываем файл Ф2 в Ф1
8) повторяем 3)-8)

Вы упускаете один существенный момент. "Последовательно" вовсе не означает "через один".
Вот вы достали из каждой очереди по элементу. Сравниваем. Один из них, который меньше, кладём в выходной поток, и подчитываем ещё один элемент из очереди, элемент которой только что отправился на выход. Т.е. может быть случай, когла вся первая последовательность уже в выходном файле, а за втоую ещё и не принимались.
Именно в этом - суть слияния.

Это сообщение отредактировал(а) Akina - 29.6.2010, 14:50