libs/sort/doc/html/sort/single_thread/spreadsort/bibliog.html

   1 <html>
   2 <head>
   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="../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>&#119926;(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_idm46048202990736.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__idm46048203222928.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__idm46048203222928.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__idm46048203222928.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 &#169; 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>