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