Всех приветствую!

Получил следующее задание: "отсортировать файл, состоящий из целых чисел, с помощью алгоритма двухпутевого двухфазного простого слияния с внутренней сортировкой ".

Проблем с организацией двухпутевого двухфазного простого слияния , ровно как и с пониманием внутренней сортировки - нет.
Пожалуйста, объясните, на кой фиг выполнять внутреннюю сортировку наряду с внешней и в какой вообще момент это делать?


Спасибо!

Dimitry Sibiryakov , т.е. для начала я разбиваю файл на два, в каждом из них использую какую-нибудь внутреннюю сортировку, а потом уже далее по алгоритму двухпутевого двухфазного простого слияния.
Я правильно понял?

Короче, фигня какая-то выходит.

1 . Предположим, у нас есть файл из n-неповторяющихся случайных целых чисел . Сортируем их с помощью двухпутевого двухфазного простого слияния :Алгоритм №1Шаг 1. Исходный файл f разбивается на два вспомогательных файла f1 и f2.

Шаг 2. Вспомогательные файлы f1 и f2 сливаются в файл f, при этом одиночные элементы образуют упорядоченные пары.

Шаг 3. Полученный файл f вновь обрабатывается, как указано в шагах 1 и 2. При этом упорядоченные пары переходят в упорядоченные четверки.

Шаг 4. Повторяя шаги, сливаем четверки в восьмерки и т.д., каждый раз удваивая длину слитых последовательностей до тех пор, пока не будет упорядочен целиком весь файл.

После выполнения i проходов получаем два файла, состоящих из серий длины 2 ⁱ . Окончание процесса происходит при выполнении условия 2 ⁱ >=nНа сортировку затратили время t1 .

2 . Также имеем файл из n-неповторяющихся случайных целых чисел . Сортируем их с помощью двухпутевого двухфазного простого слияния с предварительной внутренней сортировкой на шаге 1а:Алгоритм №2Шаг 1. Исходный файл f разбивается на два вспомогательных файла f1 и f2.

Шаг 1а. Содержимое файлов f1 и f2 сортируется с помощью внутренней сортировки.

Шаг 2. Вспомогательные файлы f1 и f2 сливаются в файл f, при этом одиночные элементы образуют упорядоченные пары.

Шаг 3. Полученный файл f вновь обрабатывается, как указано в шагах 1 и 2. При этом упорядоченные пары переходят в упорядоченные четверки.

Шаг 4. Повторяя шаги, сливаем четверки в восьмерки и т.д., каждый раз удваивая длину слитых последовательностей до тех пор, пока не будет упорядочен целиком весь файл.

После выполнения i проходов получаем два файла, состоящих из серий длины 2 ⁱ . Окончание процесса происходит при выполнении условия 2 ⁱ >=nНа сортировку затратили время t2 .

3 . А теперь предположим, что изначальный файл состоит из n-последовательных целых чисел : 1, 2 .. n.
В первом шаге Алгоритма будет два файла с упорядоченными значениями: f1 [1, 3, 5 .. n -1] и f2 [2, 4, 6 .. n] - таким образом, имитируем внутреннюю сортировку (из Алгоритма №2). Используем Алгоритм №1.
На сортировку затратили время t3 .
____________________________________________________________________________________

Что имеем.
t1 ~ t3 (ожидался знак ">"), т.к. как кол-во итераций в первом и во втором случае будет одинаковым , несмотря на то, что алгоритм в третьем примере работает с уже упорядоченными последовательностями.
t1 < t2 (ожидался знак ">") - здесь тоже всё очевидно. Во втором примере на шаг 1а тратится время, которое потом ничем не компенсируется.

Так что я вообще не понимаю прелести ускорения в указанном задании.

P.S. Ну это, конечно, всё в теории... На данный момент ожидаю, когда обработается файл из 100M чисел (во всех трёх случаях) и проверю свои догадки. Может быть итерациям рознь...

MasterZiv , перед / в процессе - не важно. В поставленной задаче внутренняя сортировка будет только увеличивать общее время сортировки.

В общем, я прогнал 100М целых чисел (~ 0.84 ГБ) для первого и третьего примера.
t1 = 3259 сек
t3 = 3050 секНевъезжающий t1 ~ t3 (ожидался знак ">"), т.к. как кол-во итераций в первом и во втором случае будет одинаковым , несмотря на то, что алгоритм в третьем примере работает с уже упорядоченными последовательностями.
Как и предполагалось...

Либо я вообще всё не так понял :-\

И кстати, гугл вообще ничего не знает про соединение внутренней и внешней сортировок. Когда задаешь подобный запрос, то выводятся туториалы, где описаны отдельно внутренние и отдельно внешние сортировки, но никак не их совместное использование.

Что-то здесь не так.