libs/sort/doc/html/sort/single_thread/spreadsort/sort_hpp/rationale/hybrid_radix.html

   1 <html>
   2 <head>
   3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
   4 <title>Hybrid Radix</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="../rationale.html" title="Rationale">
   9 <link rel="prev" href="../rationale.html" title="Rationale">
  10 <link rel="next" href="why_spreadsort.html" title="Why spreadsort?">
  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="../rationale.html"><img src="../../../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../rationale.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="why_spreadsort.html"><img src="../../../../../../../../../doc/src/images/next.png" alt="Next"></a>
  24 </div>
  25 <div class="section">
  26 <div class="titlepage"><div><div><h6 class="title">
  27 <a name="sort.single_thread.spreadsort.sort_hpp.rationale.hybrid_radix"></a><a class="link" href="hybrid_radix.html" title="Hybrid Radix">Hybrid
  28             Radix</a>
  29 </h6></div></div></div>
  30 <p>
  31               There a two primary types of radix-based sorting:
  32             </p>
  33 <p>
  34               Most-significant-digit Radix sorting (MSD) divides the data recursively
  35               based upon the top-most unsorted bits. This approach is efficient for
  36               even distributions that divide nicely, and can be done in-place (limited
  37               additional memory used). There is substantial constant overhead for
  38               each iteration to deal with the splitting structure. The algorithms
  39               provided here use MSD Radix Sort for their radix-sorting portion. The
  40               main disadvantage of MSD Radix sorting is that when the data is cut
  41               up into small pieces, the overhead for additional recursive calls starts
  42               to dominate runtime, and this makes worst-case behavior substantially
  43               worse than <span class="emphasis"><em>&#119926;(N*log(N))</em></span>.
  44             </p>
  45 <p>
  46               By contrast, <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>,
  47               <code class="literal"><code class="computeroutput"><a class="link" href="../../../../../boost/sort/spreadsort/float_so_idm46048204416688.html" title="Function template float_sort">float_sort</a></code></code>,
  48               and <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>
  49               all check to see whether Radix-based or Comparison-based sorting have
  50               better worst-case runtime, and make the appropriate recursive call.
  51               Because Comparison-based sorting algorithms are efficient on small
  52               pieces, the tendency of MSD <a href="http://en.wikipedia.org/wiki/Radix_sort" target="_top">radix
  53               sort</a> to cut the problem up small is turned into an advantage
  54               by these hybrid sorts. It is hard to conceive of a common usage case
  55               where pure MSD <a href="http://en.wikipedia.org/wiki/Radix_sort" target="_top">radix
  56               sort</a> would have any significant advantage over hybrid algorithms.
  57             </p>
  58 <p>
  59               Least-significant-digit <a href="http://en.wikipedia.org/wiki/Radix_sort" target="_top">radix
  60               sort</a> (LSD) sorts based upon the least-significant bits first.
  61               This requires a complete copy of the data being sorted, using substantial
  62               additional memory. The main advantage of LSD Radix Sort is that aside
  63               from some constant overhead and the memory allocation, it uses a fixed
  64               amount of time per element to sort, regardless of distribution or size
  65               of the list. This amount of time is proportional to the length of the
  66               radix. The other advantage of LSD Radix Sort is that it is a stable
  67               sorting algorithm, so elements with the same key will retain their
  68               original order.
  69             </p>
  70 <p>
  71               One disadvantage is that LSD Radix Sort uses the same amount of time
  72               to sort "easy" sorting problems as "hard" sorting
  73               problems, and this time spent may end up being greater than an efficient
  74               <span class="emphasis"><em>&#119926;(N*log(N))</em></span> algorithm such as <a href="http://en.wikipedia.org/wiki/Introsort" target="_top">introsort</a>
  75               spends sorting "hard" problems on large data sets, depending
  76               on the length of the datatype, and relative speed of comparisons, memory
  77               allocation, and random accesses.
  78             </p>
  79 <p>
  80               The other main disadvantage of LSD Radix Sort is its memory overhead.
  81               It's only faster for large data sets, but large data sets use significant
  82               memory, which LSD Radix Sort needs to duplicate. LSD Radix Sort doesn't
  83               make sense for items of variable length, such as strings; it could
  84               be implemented by starting at the end of the longest element, but would
  85               be extremely inefficient.
  86             </p>
  87 <p>
  88               All that said, there are places where LSD Radix Sort is the appropriate
  89               and fastest solution, so it would be appropriate to create a templated
  90               LSD Radix Sort similar 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>
  91               and <code class="literal"><code class="computeroutput"><a class="link" href="../../../../../boost/sort/spreadsort/float_so_idm46048204416688.html" title="Function template float_sort">float_sort</a></code></code>.
  92               This would be most appropriate in cases where comparisons are extremely
  93               slow.
  94             </p>
  95 </div>
  96 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
  97 <td align="left"></td>
  98 <td align="right"><div class="copyright-footer">Copyright &#169; 2014-2017 Steven
  99       Ross, Francisco Tapia, Orson Peters<p>
 100         Distributed under the <a href="http://boost.org/LICENSE_1_0.txt" target="_top">Boost
 101         Software License, Version 1.0</a>.
 102       </p>
 103 </div></td>
 104 </tr></table>
 105 <hr>
 106 <div class="spirit-nav">
 107 <a accesskey="p" href="../rationale.html"><img src="../../../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../rationale.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="why_spreadsort.html"><img src="../../../../../../../../../doc/src/images/next.png" alt="Next"></a>
 108 </div>
 109 </body>
 110 </html>