1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980 |
- [/===========================================================================
- 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]
|