Сортировка без явного задания параметров кэша: различия между версиями

Детальное экспериментальное исследование алгоритма сортировки воронкой Funnelsort без явного задания параметров кэша было выполнено в [5]. Основной результат исследования в [5] заключается в том, что грамотно реализованный алгоритм сортировки без явного задания параметров кэша может работать быстрее, чем настроенная реализация алгоритма быстрой сортировки Quicksort, для размеров входных данных, существенно превышающих объем оперативной памяти. Эта реализация также является не менее быстрой, чем недавняя реализация с явным заданием параметров кэша, включенная в тестирование. На дисковой памяти разница с алгоритмами быстрой сортировки и алгоритмами с явным заданием параметров кэша еще заметнее, хотя рассматриваемый алгоритм работает медленнее алгоритмов многосторонней сортировки слиянием Mergesort, оптимизированных для внешней памяти – таких как TPIE [6].