Прочитав [эту статью][1], я вспомнил, как писал внешнюю сортировку, которая использовала O(1) внешней памяти. Функция получала бинарый файл и максимальный размер памяти, которую она могла выделить под массив:
void ext_sort(const std::string filename, const size_t memory)
Я использовал алгоритм из [Effective Performance of External Sorting with No Additional Disk Space][2]:
1. Разделим файл на блоки, которые помещаются в доступную память. Обозначим эти блоки Block\_1, Block\_2, …, Block\_(S-1), Block\_S. Установим P = 1.
2. Читаем Block\_P в память.
3. Отсортируем данные в памяти и запишем назад в Block\_P. Установим P = P + 1, и если P ≤ S, то читаем Block\_P в память и повторяем этот шаг. Другими словами, отсортируем каждый блок файла.
4. Разделим каждый блок на меньшие блоки B\_1 и B\_2. Каждый из таких блоков занимает половину доступной памяти.
5. Читаем блок B\_1 блока Block\_1 в первую половину доступной памяти. Установим Q = 2.
6. Читаем блок B\_1 блока Block\_Q во вторую половину доступной памяти.
7. Объеденим массивы в памяти с помощью in-place слияния, запишем вторую половину памяти в блок B\_1 блока Block\_Q и установим Q = Q + 1, если Q ≤ S, читаем блок B\_1 блока Block\_Q во вторую половину доступной памяти и повторяем этот шаг.
8. Записываем первую половину доступной памяти в блок B\_1 блока Block\_1. Так как мы всегда оставляли в памяти меньшую половину элементов и провели слияние со всеми блоками, то в этой части памяти хранятся M минимальных элементы всего файла.
9. Читаем блок B\_2 блока Block\_S во вторую половину доступной памяти. Установим Q = S −1.
10. Читаем блок B\_2 блока Block\_Q в первую половину доступной памяти.
11. Объеденим массивы в памяти с помощью in-place слияния, запишем первую половину доступной памяти в блок B\_2 блока Block\_Q и установим Q = Q −1. Если Q ≥ 1 читаем блок B\_2 блока Block\_Q в первую половину доступной памяти и повторяем этот шаг.
12. Записываем вторую половину доступной памяти в блок B\_2 блока Block\_S. Аналогично шагу 8, тут хранятся максимальные элементы всего файла.
13. Начиная от блока B\_2 блока Block\_1 и до блока B\_1 блока Block\_S, определим новые блоки в файле и снова пронумеруем их Block\_1 to Block\_S. Разделим каждый блок на блоки B\_1 и B\_2. Установим P = 1.
14. Читаем B\_1 и B\_2 блока Block\_P в память. Объеденим массивы в памяти. запишем отсортированный массив назад в Block\_P и установим P = P +1. Если P ≤ S, повторяем этот шаг.
15. Если S > 1, возвращаемся к шагу 5. Каждый раз мы выделяем M минимальных и максимальных элементов, записываем их в начало и конец файла соответственно, а потом делаем то же самое с оставшимися элементами, пока не дойдем до середины файла.
Преимущество такого алгоритма, кроме отсутствия буфера на диске, это то, что с диска мы читаем данные относительно большими порциями, что ускоряет алгоритм. Реализуем алгоритм на C++. [Читать дальше →][3]
[1]:
http://habrahabr.ru/post/266557/
[2]:
https://scholar.google.co.il/scholar?cluster=7995905689817415486&hl=ru&as_sdt=0,5
[3]:
http://habrahabr.ru/post/268535/#habracut