почему сортировка слиянием предпочтительнее быстрой сортировки для сортировки связанных списков

Я прочитал на форуме следующее:

Сортировка слиянием очень эффективна для неизменяемые структуры данных, такие как связанные списки

и

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

и

при работе со связанными списками сортировка слиянием требует лишь небольшого постоянного объема вспомогательной памяти

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

60
задан maxpayne 7 March 2011 в 17:40
поделиться