внешняя сортировка с k-way merging против быстрой сортировки

Question

Какой из них лучше? Скажем, 1 ГБ памяти и 100 ГБ файла для сортировки.

Один случай слияния с 10 путями: - 100 нагрузок по 1 ГБ, за которыми следуют 10 * 10 + 10 * 100 по 100 МБ (для 10-полосной, а затем 10-полосной объединения)

Для быстрой сортировки требуется 100 * 7 * 2 (nlogn) 1 ГБ загрузки?

Answer 1

Сортировка слиянием более эффективна при обработке больших данных.

Причина в том, что быстрая сортировка - это подход сверху вниз, Это означает, что сначала нужно обработать 100 ГБ, а затем обработать 50 ГБ * 2 ... невозможно хранить целые данные в памяти, когда у вас большие данные.

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

Answer 2

Основным узким местом будет чтение и запись на жесткий диск. Мы читаем каждый элемент с жесткого диска дважды и записываем каждый элемент с жесткого диска дважды. Один раз для сортировки кусков, а затем еще раз для многократного слияния.

Напротив, быстрая сортировка будет читать / записывать каждый элемент на жесткий диск в среднем за O (log n) раз.