1[/=========================================================================== 2 Copyright (c) 2017 Steven Ross, Francisco Tapia, Orson Peters 3 4 5 Distributed under the Boost Software License, Version 1.0 6 See accompanying file LICENSE_1_0.txt or copy at 7 http://www.boost.org/LICENSE_1_0.txt 8=============================================================================/] 9 10 11[section:bibliography 4.- Bibliography] 12 13[*Steven Ross] 14 15[h4 Standard Template Library Sort Algorithms] 16 17[@http://www.cplusplus.com/reference/algorithm/sort/ C++ STL sort algorithms]. 18 19[h4 Radix Sort] 20 21A type of algorithm that sorts based upon distribution instead of by comparison. 22Wikipedia has an article about Radix Sorting. 23A more detailed description of various Radix Sorting algorithms is provided here: 24 25Donald Knuth. The Art of Computer Programming, 26Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. 27ISBN 0-201-89685-0. Section 5.2.5: Sorting by Distribution, pp.168-179. 28 29[h4 Introsort] 30 31A high-speed comparison-based sorting algorithm that takes ['[bigo](N * log(N))] time. 32See __introsort and 33Musser, David R. (1997). "Introspective Sorting and Selection Algorithms", 34Software: Practice and Experience (Wiley) 27 (8), pp 983-993, 35available at [@http://www.cs.rpi.edu/~musser/gp/introsort.ps Musser Introsort]. 36 37[h4 American Flag Sort] 38 39A high-speed hybrid string sorting algorithm that __string_sort is partially based 40upon. See __american_flag and Peter M. McIlroy, Keith Bostic, M. Douglas McIlroy. Engineering Radix Sort, Computing Systems 1993. 41 42[h4 Adaptive Left Radix (ARL)] 43 44ARL (Adaptive Left Radix) is a hybrid cache-friendly integer sorting algorithm 45with comparable speed on random data to __integer_sort, 46but does not have the optimizations for worst-case performance, 47causing it to perform poorly on certain types of unevenly distributed data. 48 49Arne Maus, [@http://www.nik.no/2002/Maus.pdf ARL, a faster in-place, cache friendly sorting algorithm], 50presented at NIK2002, Norwegian Informatics Conference, Kongsberg, 2002. Tapir, ISBN 82-91116-45-8. 51 52[h4 Original Spreadsort] 53 54The algorithm that __integer_sort was originally based on. 55__integer_sort uses a smaller number of key bits at a time for better cache efficiency 56than the method described in the paper. 57The importance of cache efficiency grew as CPU clock speeds increased 58while main memory latency stagnated. 59See Steven J. Ross, 60The Spreadsort High-performance General-case Sorting Algorithm, 61Parallel and Distributed Processing Techniques and Applications, Volume 3, pp.1100-1106. Las Vegas Nevada. 2002. See 62[@../../doc/papers/original_spreadsort06_2002.pdf Steven Ross spreadsort_2002]. 63 64[*Francisco Tapia] 65 66[01] Introduction to Algorithms, 3rd Edition (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein) 67 68[02] C++ STL Sort Algorithms 69 70[03] Algorithm + Data Structures = Programs ( Nicklaus Wirth) Prentice Hall Series in Automatic Computation 71 72[4] Structured Parallel Programming: Patterns for Efficient Computation (Michael McCool, James Reinders, Arch Robison) 73 74 75[*Orson Peters] 76 77[endsect] 78 79 80 81