1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 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>��(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__idm45878544022768.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_idm45878545215024.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_idm45878543797168.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>��(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__idm45878544022768.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_idm45878545215024.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 © 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> 111
