Предположим, что нам нужно внешне отсортировать некоторый большой набор чисел. Мы хотим рассмотреть 2 случая:
- 4 ленты: 2 входные ленты, 2 выходные
- 3 ленты: 2 вп, 1 изн
Дело 1:
Мы начинаем с k прогонов, затем копируем эти прогоны на 2 входные ленты (слева на рис. ниже), на каждой итерации мы берем два разных прогона с входных лент, объединяем (и сортируем) их и за одну итерацию сохраняем на первую выходную ленту, а в следующей итерации - на вторую, как показано ниже. Затем меняем выходные ленты на входные и повторяем процедуру. Итак, если у нас есть, скажем, n=10^6 элементов и k=1000 прогонов, то после первой фазы размер прогона будет 2000, после третьего 4000 и так далее. Таким образом, общее количество фаз равно ceil(log_2(n)).
Случай 2:
В наилучшем случае сложности количество фаз равно position of Fibonacci’s number in the Fibonacci’s sequence minus two, т.е. если у нас начальное количество прогонов k=34 и 34 — 9-е число в последовательности Фибоначчи, то у нас будет 7 фаз.
Но… если наше количество прогонов не является числом Фибоначчи, необходимо дополнить ленту фиктивными прогонами, чтобы получить «нет». пробегов до числа Фибоначчи.
Наконец, мой вопрос:
Какое среднее количество фаз необходимо для сортировки последовательности, если количество прогонов не является числом Фибоначчи?
