81 lines
3.0 KiB
Plaintext
81 lines
3.0 KiB
Plaintext
[/===========================================================================
|
|
Copyright (c) 2017 Steven Ross, Francisco Tapia, Orson Peters
|
|
|
|
|
|
Distributed under the Boost Software License, Version 1.0
|
|
See accompanying file LICENSE_1_0.txt or copy at
|
|
http://www.boost.org/LICENSE_1_0.txt
|
|
=============================================================================/]
|
|
|
|
|
|
[section:bibliography 4.- Bibliography]
|
|
|
|
[*Steven Ross]
|
|
|
|
[h4 Standard Template Library Sort Algorithms]
|
|
|
|
[@http://www.cplusplus.com/reference/algorithm/sort/ C++ STL sort algorithms].
|
|
|
|
[h4 Radix Sort]
|
|
|
|
A type of algorithm that sorts based upon distribution instead of by comparison.
|
|
Wikipedia has an article about Radix Sorting.
|
|
A more detailed description of various Radix Sorting algorithms is provided here:
|
|
|
|
Donald Knuth. The Art of Computer Programming,
|
|
Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998.
|
|
ISBN 0-201-89685-0. Section 5.2.5: Sorting by Distribution, pp.168-179.
|
|
|
|
[h4 Introsort]
|
|
|
|
A high-speed comparison-based sorting algorithm that takes ['[bigo](N * log(N))] time.
|
|
See __introsort and
|
|
Musser, David R. (1997). "Introspective Sorting and Selection Algorithms",
|
|
Software: Practice and Experience (Wiley) 27 (8), pp 983-993,
|
|
available at [@http://www.cs.rpi.edu/~musser/gp/introsort.ps Musser Introsort].
|
|
|
|
[h4 American Flag Sort]
|
|
|
|
A high-speed hybrid string sorting algorithm that __string_sort is partially based
|
|
upon. See __american_flag and Peter M. McIlroy, Keith Bostic, M. Douglas McIlroy. Engineering Radix Sort, Computing Systems 1993.
|
|
|
|
[h4 Adaptive Left Radix (ARL)]
|
|
|
|
ARL (Adaptive Left Radix) is a hybrid cache-friendly integer sorting algorithm
|
|
with comparable speed on random data to __integer_sort,
|
|
but does not have the optimizations for worst-case performance,
|
|
causing it to perform poorly on certain types of unevenly distributed data.
|
|
|
|
Arne Maus, [@http://www.nik.no/2002/Maus.pdf ARL, a faster in-place, cache friendly sorting algorithm],
|
|
presented at NIK2002, Norwegian Informatics Conference, Kongsberg, 2002. Tapir, ISBN 82-91116-45-8.
|
|
|
|
[h4 Original Spreadsort]
|
|
|
|
The algorithm that __integer_sort was originally based on.
|
|
__integer_sort uses a smaller number of key bits at a time for better cache efficiency
|
|
than the method described in the paper.
|
|
The importance of cache efficiency grew as CPU clock speeds increased
|
|
while main memory latency stagnated.
|
|
See Steven J. Ross,
|
|
The Spreadsort High-performance General-case Sorting Algorithm,
|
|
Parallel and Distributed Processing Techniques and Applications, Volume 3, pp.1100-1106. Las Vegas Nevada. 2002. See
|
|
[@../../doc/papers/original_spreadsort06_2002.pdf Steven Ross spreadsort_2002].
|
|
|
|
[*Francisco Tapia]
|
|
|
|
[01] Introduction to Algorithms, 3rd Edition (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein)
|
|
|
|
[02] C++ STL Sort Algorithms
|
|
|
|
[03] Algorithm + Data Structures = Programs ( Nicklaus Wirth) Prentice Hall Series in Automatic Computation
|
|
|
|
[4] Structured Parallel Programming: Patterns for Efficient Computation (Michael McCool, James Reinders, Arch Robison)
|
|
|
|
|
|
[*Orson Peters]
|
|
|
|
[endsect]
|
|
|
|
|
|
|