Standard Template Library Sort Algorithms

С++ алгоритмы сортировки STL.

Radix Sort

Тип алгоритма, который сортируется на основе распределения, а не сравнения. В Википедии есть статья о Radix Sorting. Более подробное описание различных алгоритмов сортировки Radix приведено здесь:

Дональд Кнут. Искусство компьютерного программирования, том 3: Сортировка и поиск, второе издание. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 5.2.5: Sorting by Distribution, pp.168-179.

Introsort

Высокоскоростной алгоритм сортировки на основе сравнения, который использует𝑶(N * log(N))Время. См.introsortand Musser, David R. (1997). "Introspective Sorting and Selection Algorithms", Software: Practice and Experience (Wiley) 27 (8), pp 983-993, available atMusser Introsort.

American Flag Sort

Высокоскоростной гибридный алгоритм сортировки струн, на котором частично основанstring_sort. См.Американский сорт флагаи Питер М. Макилрой, Кит Бостик, М. Дуглас Макилрой. Инженерные системы Radix Sort, 1993.

Adaptive Left Radix (ARL)

ARL (Adaptive Left Radix) - это гибридный алгоритм сортировки целых чисел с сопоставимой скоростью на случайных данных.integer_sort, но не имеет оптимизаций для наихудшей производительности, в результате чего он плохо работает на определенных типах неравномерно распределенных данных.

Arne Maus,ARL, более быстрый алгоритм сортировки кэша, представленный на NIK2002, Norwegian Informatics Conference, Kongsberg, 2002. Тапир, ИСБН 82-91116-45-8.

Original Spreadsort

Алгоритм, на которомinteger_sortбыл первоначально основан.integer_sortиспользует меньшее количество ключевых битов за раз для лучшей эффективности кэша, чем метод, описанный в статье. Важность эффективности кэша росла по мере увеличения тактовой частоты процессора, в то время как задержка основной памяти стагнировала. См. Steven J. Ross, The Spreadsort High Performance General-case Sorting Algorithm, Parallel and Distributed Processing Techniques and Applications, Volume 3, pp.1100-1106. Лас-Вегас, Невада. 2002. См.Steven Ross spreadsort_2002.