3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
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="../index.html" title="Boost.Sort">
9 <link rel="prev" href="acks.html" title="Acknowledgements">
10 <link rel="next" href="history.html" title="History">
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>
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="../index.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>
26 <div class="titlepage"><div><div><h2 class="title" style="clear: both">
27 <a name="sort.bibliog"></a><a class="link" href="bibliog.html" title="Bibliography">Bibliography</a>
28 </h2></div></div></div>
30 <a name="sort.bibliog.h0"></a>
31 <span class="phrase"><a name="sort.bibliog.standard_template_library_sort_a"></a></span><a class="link" href="bibliog.html#sort.bibliog.standard_template_library_sort_a">Standard
32 Template Library Sort Algorithms</a>
35 <a href="http://www.cplusplus.com/reference/algorithm/sort/" target="_top">C++ STL sort
39 <a name="sort.bibliog.h1"></a>
40 <span class="phrase"><a name="sort.bibliog.radix_sort"></a></span><a class="link" href="bibliog.html#sort.bibliog.radix_sort">Radix
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 of
46 various Radix Sorting algorithms is provided here:
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: Sorting
51 by Distribution, pp.168-179.
54 <a name="sort.bibliog.h2"></a>
55 <span class="phrase"><a name="sort.bibliog.introsort"></a></span><a class="link" href="bibliog.html#sort.bibliog.introsort">Introsort</a>
58 A high-speed comparison-based sorting algorithm that takes <span class="emphasis"><em>𝑶(N * log(N))</em></span>
59 time. See <a href="http://en.wikipedia.org/wiki/Introsort" target="_top">introsort</a>
60 and Musser, David R. (1997). "Introspective Sorting and Selection Algorithms",
61 Software: Practice and Experience (Wiley) 27 (8), pp 983-993, available at
62 <a href="http://www.cs.rpi.edu/~musser/gp/introsort.ps" target="_top">Musser Introsort</a>.
65 <a name="sort.bibliog.h3"></a>
66 <span class="phrase"><a name="sort.bibliog.american_flag_sort"></a></span><a class="link" href="bibliog.html#sort.bibliog.american_flag_sort">American
70 A high-speed hybrid string sorting algorithm that <code class="literal"><code class="computeroutput"><a class="link" href="../boost/sort/spreadsort/string_sort_idp26036384.html" title="Function template string_sort">string_sort</a></code></code>
71 is partially based upon. See <a href="http://en.wikipedia.org/wiki/American_flag_sort" target="_top">American
72 flag sort</a> and Peter M. McIlroy, Keith Bostic, M. Douglas McIlroy. Engineering
73 Radix Sort, Computing Systems 1993.
76 <a name="sort.bibliog.h4"></a>
77 <span class="phrase"><a name="sort.bibliog.adaptive_left_radix_arl"></a></span><a class="link" href="bibliog.html#sort.bibliog.adaptive_left_radix_arl">Adaptive
81 ARL (Adaptive Left Radix) is a hybrid cache-friendly integer sorting algorithm
82 with comparable speed on random data to <code class="literal"><code class="computeroutput"><a class="link" href="../boost/sort/spreadsort/integer_sort_idp18898880.html" title="Function template integer_sort">integer_sort</a></code></code>,
83 but does not have the optimizations for worst-case performance, causing it
84 to perform poorly on certain types of unevenly distributed data.
87 Arne Maus, <a href="http://www.nik.no/2002/Maus.pdf" target="_top">ARL, a faster in-place,
88 cache friendly sorting algorithm</a>, presented at NIK2002, Norwegian Informatics
89 Conference, Kongsberg, 2002. Tapir, ISBN 82-91116-45-8.
92 <a name="sort.bibliog.h5"></a>
93 <span class="phrase"><a name="sort.bibliog.original_spreadsort"></a></span><a class="link" href="bibliog.html#sort.bibliog.original_spreadsort">Original
97 The algorithm that <code class="literal"><code class="computeroutput"><a class="link" href="../boost/sort/spreadsort/integer_sort_idp18898880.html" title="Function template integer_sort">integer_sort</a></code></code>
98 was originally based on. <code class="literal"><code class="computeroutput"><a class="link" href="../boost/sort/spreadsort/integer_sort_idp18898880.html" title="Function template integer_sort">integer_sort</a></code></code>
99 uses a smaller number of key bits at a time for better cache efficiency than
100 the method described in the paper. The importance of cache efficiency grew
101 as CPU clock speeds increased while main memory latency stagnated. See Steven
102 J. Ross, The Spreadsort High-performance General-case Sorting Algorithm, Parallel
103 and Distributed Processing Techniques and Applications, Volume 3, pp.1100-1106.
104 Las Vegas Nevada. 2002. See <a href="../../../doc/papers/original_spreadsort06_2002.pdf" target="_top">Steven
105 Ross spreadsort_2002</a>.
108 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
109 <td align="left"></td>
110 <td align="right"><div class="copyright-footer">Copyright © 2014 Steven Ross<p>
111 Distributed under the <a href="http://boost.org/LICENSE_1_0.txt" target="_top">Boost
112 Software License, Version 1.0</a>.
117 <div class="spirit-nav">
118 <a accesskey="p" href="acks.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.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>