Как определить оптимальный размер файла для сортировки слияния?

Question

Большинство из вас это осознает, но для меня это стало неожиданностью: быстрее сортировать (например) 96 файлов каждый размер 4Mb, чем 6 файлов 64Mb с использованием mergesort (с общим объемом информации) , Я случайно наткнулся на это открытие. Таким образом, возникает вопрос, каков оптимальный размер входного файла для mergesort?

Я предполагаю, что между временем сортировки (осью y) и количеством файлов (ось x) будет существовать связь между линией завихрения. Есть ли алгоритм, это больше эмпирическое правило или просто попытка установить несколько разных размеров файлов? Очевидные факторы, которые будут влиять на это: * Максимальное количество файлов, которые ОС может открывать одновременно.
* скорость чтения/записи жесткого диска

Любые ссылки приветствуются!

Answer 1

Если ваша сортировка включает в себя перемещение файлов, то обычные меры для «быстрого» алгоритма сортировки на самом деле не применяются. Для перемещения файлов вокруг более быстрый алгоритм сортировки будет заключаться в минимизации количества файлов.

Сортировка сортировки может использоваться и имеет очень близкое к минимальному количеству свопов, но, в худшем случае, каждый файл должен быть написан дважды: один раз, когда он заменен на место, чтобы сделать место для файл, который там есть, и однажды поменялся на место, которое должно быть, когда придет время.

Существует алгоритм, который выполняет не более n + 1 присвоений. «Обмен» (который используется большинством алгоритмов сортировки) включает три назначения (с использованием временной переменной). Это работает в значительной степени, делая сортировку без фактического обмена чем-либо. Путем записи каждого выбранного элемента в новую память или сохранения порядка сортировки в памяти, а затем реорганизации файлов в том же пространстве памяти после факта (стиль дефрагментации). Этот алгоритм действительно был бы минимальным с точки зрения копирования данных. Это идеально, когда копирование предметов дорого (сортировка данных на диске).