Внешняя сортировка с k-way merging против быстрой сортировки
Какой из них лучше? Скажем, 1 ГБ памяти и 100 ГБ файла для сортировки.
Один случай потребности в 10-полосном объединении: - 100 загрузок по 1 ГБ с последующими 10*10 + 10*100 нагрузками по 100 МБ (для 10-полосных операций с последующим 10-полосным объединением)
Для быстрой сортировки требуется 100*7*2 (nlogn) 1ГБ?
2 ответа
Сортировка слиянием более эффективна при обработке больших данных.
Причина в том, что быстрая сортировка - это подход "сверху вниз", что означает, что сначала нужно обработать 100 ГБ, а затем обработать 50 ГБ * 2 ... невозможно поместить целые данные в память, когда у вас большие данные.
иначе сортировка слиянием - это подход снизу вверх, как вы уже описали, вы можете разделить данные на небольшие партии, которые могут поместиться в память, и объединить их в буфере.
Основным узким местом будет чтение и запись на жесткий диск. Мы читаем каждый элемент с жесткого диска дважды и записываем каждый элемент с жесткого диска дважды. Один раз для сортировки кусков, а затем еще раз для многократного слияния.
Напротив, быстрая сортировка будет считывать / записывать каждый элемент на жесткий диск в среднем O(log n) раз.