1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 4<title>Bibliography</title> 5<link rel="stylesheet" href="../../../../../../../doc/src/boostbook.css" type="text/css"> 6<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 7<link rel="home" href="../../../index.html" title="Boost.Sort"> 8<link rel="up" href="../spreadsort.html" title="2.1.-Spreadsort"> 9<link rel="prev" href="acks.html" title="Acknowledgements"> 10<link rel="next" href="history.html" title="History"> 11</head> 12<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 13<table cellpadding="2" width="100%"><tr> 14<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../../boost.png"></td> 15<td align="center"><a href="../../../../../../../index.html">Home</a></td> 16<td align="center"><a href="../../../../../../../libs/libraries.htm">Libraries</a></td> 17<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 18<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 19<td align="center"><a href="../../../../../../../more/index.htm">More</a></td> 20</tr></table> 21<hr> 22<div class="spirit-nav"> 23<a accesskey="p" href="acks.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../spreadsort.html"><img src="../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../index.html"><img src="../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="history.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a> 24</div> 25<div class="section"> 26<div class="titlepage"><div><div><h4 class="title"> 27<a name="sort.single_thread.spreadsort.bibliog"></a><a class="link" href="bibliog.html" title="Bibliography">Bibliography</a> 28</h4></div></div></div> 29<h5> 30<a name="sort.single_thread.spreadsort.bibliog.h0"></a> 31 <span class="phrase"><a name="sort.single_thread.spreadsort.bibliog.standard_template_library_sort_a"></a></span><a class="link" href="bibliog.html#sort.single_thread.spreadsort.bibliog.standard_template_library_sort_a">Standard 32 Template Library Sort Algorithms</a> 33 </h5> 34<p> 35 <a href="http://www.cplusplus.com/reference/algorithm/sort/" target="_top">C++ STL 36 sort algorithms</a>. 37 </p> 38<h5> 39<a name="sort.single_thread.spreadsort.bibliog.h1"></a> 40 <span class="phrase"><a name="sort.single_thread.spreadsort.bibliog.radix_sort"></a></span><a class="link" href="bibliog.html#sort.single_thread.spreadsort.bibliog.radix_sort">Radix 41 Sort</a> 42 </h5> 43<p> 44 A type of algorithm that sorts based upon distribution instead of by comparison. 45 Wikipedia has an article about Radix Sorting. A more detailed description 46 of various Radix Sorting algorithms is provided here: 47 </p> 48<p> 49 Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, 50 Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 5.2.5: 51 Sorting by Distribution, pp.168-179. 52 </p> 53<h5> 54<a name="sort.single_thread.spreadsort.bibliog.h2"></a> 55 <span class="phrase"><a name="sort.single_thread.spreadsort.bibliog.introsort"></a></span><a class="link" href="bibliog.html#sort.single_thread.spreadsort.bibliog.introsort">Introsort</a> 56 </h5> 57<p> 58 A high-speed comparison-based sorting algorithm that takes <span class="emphasis"><em>��(N 59 * log(N))</em></span> time. See <a href="http://en.wikipedia.org/wiki/Introsort" target="_top">introsort</a> 60 and Musser, David R. (1997). "Introspective Sorting and Selection 61 Algorithms", Software: Practice and Experience (Wiley) 27 (8), pp 62 983-993, available at <a href="http://www.cs.rpi.edu/~musser/gp/introsort.ps" target="_top">Musser 63 Introsort</a>. 64 </p> 65<h5> 66<a name="sort.single_thread.spreadsort.bibliog.h3"></a> 67 <span class="phrase"><a name="sort.single_thread.spreadsort.bibliog.american_flag_sort"></a></span><a class="link" href="bibliog.html#sort.single_thread.spreadsort.bibliog.american_flag_sort">American 68 Flag Sort</a> 69 </h5> 70<p> 71 A high-speed hybrid string sorting algorithm that <code class="literal"><code class="computeroutput"><a class="link" href="../../../boost/sort/spreadsort/string_s_idm45878543797168.html" title="Function template string_sort">string_sort</a></code></code> 72 is partially based upon. See <a href="http://en.wikipedia.org/wiki/American_flag_sort" target="_top">American 73 flag sort</a> and Peter M. McIlroy, Keith Bostic, M. Douglas McIlroy. 74 Engineering Radix Sort, Computing Systems 1993. 75 </p> 76<h5> 77<a name="sort.single_thread.spreadsort.bibliog.h4"></a> 78 <span class="phrase"><a name="sort.single_thread.spreadsort.bibliog.adaptive_left_radix_arl"></a></span><a class="link" href="bibliog.html#sort.single_thread.spreadsort.bibliog.adaptive_left_radix_arl">Adaptive 79 Left Radix (ARL)</a> 80 </h5> 81<p> 82 ARL (Adaptive Left Radix) is a hybrid cache-friendly integer sorting algorithm 83 with comparable speed on random data to <code class="literal"><code class="computeroutput"><a class="link" href="../../../boost/sort/spreadsort/integer__idm45878544022768.html" title="Function template integer_sort">integer_sort</a></code></code>, 84 but does not have the optimizations for worst-case performance, causing 85 it to perform poorly on certain types of unevenly distributed data. 86 </p> 87<p> 88 Arne Maus, <a href="http://www.nik.no/2002/Maus.pdf" target="_top">ARL, a faster in-place, 89 cache friendly sorting algorithm</a>, presented at NIK2002, Norwegian 90 Informatics Conference, Kongsberg, 2002. Tapir, ISBN 82-91116-45-8. 91 </p> 92<h5> 93<a name="sort.single_thread.spreadsort.bibliog.h5"></a> 94 <span class="phrase"><a name="sort.single_thread.spreadsort.bibliog.original_spreadsort"></a></span><a class="link" href="bibliog.html#sort.single_thread.spreadsort.bibliog.original_spreadsort">Original 95 Spreadsort</a> 96 </h5> 97<p> 98 The algorithm that <code class="literal"><code class="computeroutput"><a class="link" href="../../../boost/sort/spreadsort/integer__idm45878544022768.html" title="Function template integer_sort">integer_sort</a></code></code> 99 was originally based on. <code class="literal"><code class="computeroutput"><a class="link" href="../../../boost/sort/spreadsort/integer__idm45878544022768.html" title="Function template integer_sort">integer_sort</a></code></code> 100 uses a smaller number of key bits at a time for better cache efficiency 101 than the method described in the paper. The importance of cache efficiency 102 grew as CPU clock speeds increased while main memory latency stagnated. 103 See Steven J. Ross, The Spreadsort High-performance General-case Sorting 104 Algorithm, Parallel and Distributed Processing Techniques and Applications, 105 Volume 3, pp.1100-1106. Las Vegas Nevada. 2002. See <a href="../../../../../doc/papers/original_spreadsort06_2002.pdf" target="_top">Steven 106 Ross spreadsort_2002</a>. 107 </p> 108</div> 109<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 110<td align="left"></td> 111<td align="right"><div class="copyright-footer">Copyright © 2014-2017 Steven 112 Ross, Francisco Tapia, Orson Peters<p> 113 Distributed under the <a href="http://boost.org/LICENSE_1_0.txt" target="_top">Boost 114 Software License, Version 1.0</a>. 115 </p> 116</div></td> 117</tr></table> 118<hr> 119<div class="spirit-nav"> 120<a accesskey="p" href="acks.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../spreadsort.html"><img src="../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../index.html"><img src="../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="history.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a> 121</div> 122</body> 123</html> 124
