Изменения

=== Сортировка ===

Поскольку мы легко умеем выполнять слияние упорядоченных последовательностей, то логичным шагом будет рассмотреть сортировку во внешней памяти. Рассмотрим некоторую модификацию алгоритма Merge sort. В стандартном алгоритме все элементы разбиваются на пары, после чего сливаются в упорядоченные последовательности длины 2, те в свою очередь сливаются в последовательности длины 4 и т.д. (для простоты в данном алгоритме будем считать что N это степень двойки). Во внешней памяти не выгодно начинать с последовательностей длины 1, так как чтение происходит блоками длины B. Вместо этого можно целиком считать блок и отсортировать его во внутренней памяти. Тогда количество листьев в дереве сортировки будет не N, а <tex>\dfrac{N}{B}</tex>. Помимо этого, гораздо выгоднее сливать больше чем 2 списка за раз, чтобы уменьшить высоту дерева сортировки. Так как оперативная память размера M, то можно сливать сразу <tex>\dfrac{M}{B}</tex> списков. Итого, на каждом уровне дерева сортировки мы выполняем <tex>\mathcal{O}\left(\dfrac{N}{B}\right)</tex> операций и итоговая сложность {{---}} <tex>\mathcal{O}\left(\dfrac{N}{B}\log_{\frac{M}{B}}\dfrac{N}{B}\right) = Sort(N)</tex>.

В качестве небольшой оптимизации можно в начале сортировать во внутренней памяти последовательности длины M, а не B. Хотя итоговая сложность и станет <tex>\mathcal{O}\left(\dfrac{N}{B}\log_{\frac{M}{B}}\dfrac{N}{M}\right)</tex>, но это уменьшит высоту дерева сортировки всего на единицу, что не очень сильно скажется на времени работы.