Быстрая сортировка хорошо работает для сортировки на месте.В частности, большинство операций может быть определено с помощью замены пар элементов в массиве.Однако, чтобы сделать это, вы обычно «ходите» по массиву с двумя указателями (или индексами и т. Д.). Один начинается в начале массива, а другой - в конце.Затем оба продвигаются к середине (и вы закончите с определенным шагом раздела, когда они встретятся).Это дорого обходится с файлами, потому что файлы ориентированы в основном на чтение в одном направлении, от начала до конца.Начало с конца и поиск назад, как правило, относительно дороги.
По крайней мере в самом простом воплощении сортировка слиянием в значительной степени противоположна.Простой способ реализовать это требует только просмотра данных в одном направлении, , но включает в себя разбиение данных на две отдельные части, сортировку частей, а затем объединение их вместе.
С помощьюсвязанный список, легко взять (например) чередующиеся элементы в одном связанном списке и манипулировать ссылками, чтобы вместо этого создать два связанных списка из этих же элементов.С массивом переставить элементы так, чтобы чередующиеся элементы помещались в отдельные массивы, легко, если вы хотите создать копию размером с исходные данные, но в остальном довольно нетривиально.
Аналогично, слияние с массивамиЛегко, если вы объединяете элементы из исходных массивов в новый массив с порядком данных, но сделать это на месте без создания новой копии данных - это совсем другая история.Со связанным списком объединение элементов из двух исходных списков в один целевой список является тривиальным - опять же, вы просто манипулируете ссылками, не копируя элементы.
Что касается использования быстрой сортировки для создания отсортированных прогонов для внешнегосортировка слиянием, она работает, но, как правило, она (безусловно) неоптимальна.Чтобы оптимизировать сортировку слиянием, вы обычно хотите максимизировать длину каждого отсортированного «прогона» при его создании.Если вы просто прочитаете данные, которые уместятся в памяти, быстро отсортируете их и запишите их, каждый прогон будет ограничен (чуть меньше) размером доступной памяти.
Вы можете сделать довольнонемного лучше, чем это, как правило, хотя.Вы начинаете с чтения блока данных, но вместо использования быстрой сортировки вы создаете кучу.Затем, когда вы записываете каждый элемент из кучи в отсортированный файл «run», вы читаете другой элемент из вашего входного файла.Если он больше, чем элемент, который вы только что записали на диск, вы вставляете его в существующую кучу и повторяете.
Элементы меньшего размера (т. Е. Принадлежащие ранее элементам, которые уже были записаны), которые вы храните отдельно, ивстроить вторую кучу.Когда (и только когда) ваша первая куча пуста, а вторая куча заняла всю память, вы прекращаете запись элементов в существующий файл «run» и запускаете новый.
Точно, какЭффективность этого будет зависеть от начального порядка данных.В худшем случае (входные данные отсортированы в обратном порядке) это совсем не помогает.В лучшем случае (вход уже отсортирован) он позволяет вам «сортировать» данные за один проход через ввод.В среднем случае (ввод в случайном порядке) он позволяет приблизительно удвоить длину каждого отсортированного прогона, что обычно увеличивает скорость на примерно на 20-25% (хотя процентное соотношение варьируется в зависимости от того, насколько больше вашданные больше доступной памяти).