Комментарии 9
Не совсем. In-place merge sort это вариант сортировки слиянием, который не использует внешний буфер. При этом весь массив находится в памяти.
Для внешней сортировки (когда данные не помещаются в памяти) нельзя использовать те же алгоритмы, это будет слишком медленно. Этот алгоритм — внешняя сортировка, точнее, её вариант, не требующий буфера на диске. Он может пригодится, например, если вам нужно отсортировать 980Гб данных на терабайтном диске (хотя это и займет кучу времени, судя по всему).
Для внешней сортировки (когда данные не помещаются в памяти) нельзя использовать те же алгоритмы, это будет слишком медленно. Этот алгоритм — внешняя сортировка, точнее, её вариант, не требующий буфера на диске. Он может пригодится, например, если вам нужно отсортировать 980Гб данных на терабайтном диске (хотя это и займет кучу времени, судя по всему).
А зачем вы делаете
new std::vector<T>? Это никак не влияет на скорость/пам'ять?
Что будет, если между new и delete будет выброшено исключение?
Что будет, если условие не выполняется?
Что будет, если условие не выполняется?
std::is_trivially_copyable<T>::value == false
Сколько получается операций слияния блоков? O(S^2), или, всё-таки, меньше?
O(S^2): Мы делаем S проходов, и для каждого K от 1 до S делаем S-1 слияний с первым блоком и столько же с последним. Получается S(S-1) слияний.
То есть, получается сложность O(N*S*log(N/S)). Многовато…
С помощью блочного in-place merge улучшить её, конечно, не получится: при поиске следующего блока придётся проходить по всему файлу, а чтение первой и последней записи работает ненамного быстрее, чем чтение блока целиком.
Впрочем, есть и другой, более простой вариант in-place merge sort. Правда, использовать его для файла не очень удобно.
Но должно быть легко реализовать обычный quicksort: при разделении очередного фрагмента подгружаете в память его начало и конец, а потом двигаете их навстречу пока они не сомкнутся. Когда маленький фрагмент умещается в память — сортируете его там целиком. Получится O(S*log(S)) чтений/записей блока.
С помощью блочного in-place merge улучшить её, конечно, не получится: при поиске следующего блока придётся проходить по всему файлу, а чтение первой и последней записи работает ненамного быстрее, чем чтение блока целиком.
Впрочем, есть и другой, более простой вариант in-place merge sort. Правда, использовать его для файла не очень удобно.
Но должно быть легко реализовать обычный quicksort: при разделении очередного фрагмента подгружаете в память его начало и конец, а потом двигаете их навстречу пока они не сомкнутся. Когда маленький фрагмент умещается в память — сортируете его там целиком. Получится O(S*log(S)) чтений/записей блока.
stxxl
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Внешняя сортировка с O(1) дополнительной памяти