Внешняя сортировка с O(1) дополнительной памяти

[Ramires]

Если я верно понял, это вариация "In-place merge sort"?

Да, надо читать теги.

[Randl]

Не совсем. In-place merge sort это вариант сортировки слиянием, который не использует внешний буфер. При этом весь массив находится в памяти.
Для внешней сортировки (когда данные не помещаются в памяти) нельзя использовать те же алгоритмы, это будет слишком медленно. Этот алгоритм — внешняя сортировка, точнее, её вариант, не требующий буфера на диске. Он может пригодится, например, если вам нужно отсортировать 980Гб данных на терабайтном диске (хотя это и займет кучу времени, судя по всему).

[Door]

А зачем вы делаете new std::vector<T>? Это никак не влияет на скорость/пам'ять?

[3Hren]

Влияет и, более того, бессмысленно.

Из серии Yo dawg, I heard you like to allocate on heap so we put your vector on heap so you can allocate on heap while allocating on heap.

[3Hren]

Что будет, если между new и delete будет выброшено исключение?
Что будет, если условие не выполняется?

std::is_trivially_copyable<T>::value == false

[Mrrl]

Сколько получается операций слияния блоков? O(S^2), или, всё-таки, меньше?

[Randl]

O(S^2): Мы делаем S проходов, и для каждого K от 1 до S делаем S-1 слияний с первым блоком и столько же с последним. Получается S(S-1) слияний.

[Mrrl]

То есть, получается сложность O(N*S*log(N/S)). Многовато…
С помощью блочного in-place merge улучшить её, конечно, не получится: при поиске следующего блока придётся проходить по всему файлу, а чтение первой и последней записи работает ненамного быстрее, чем чтение блока целиком.
Впрочем, есть и другой, более простой вариант in-place merge sort. Правда, использовать его для файла не очень удобно.
Но должно быть легко реализовать обычный quicksort: при разделении очередного фрагмента подгружаете в память его начало и конец, а потом двигаете их навстречу пока они не сомкнутся. Когда маленький фрагмент умещается в память — сортируете его там целиком. Получится O(S*log(S)) чтений/записей блока.

[Sonic_SE]

stxxl