libs/sort/doc/html/index.html

   1 <html>
   2 <head>
   3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
   4 <title>Boost.Sort</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="next" href="sort/single_thread.html" title="2.- Single Thread Algorithms">
   9 </head>
  10 <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
  11 <table cellpadding="2" width="100%"><tr>
  12 <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../boost.png"></td>
  13 <td align="center"><a href="../../../../index.html">Home</a></td>
  14 <td align="center"><a href="../../../../libs/libraries.htm">Libraries</a></td>
  15 <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
  16 <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
  17 <td align="center"><a href="../../../../more/index.htm">More</a></td>
  18 </tr></table>
  19 <hr>
  20 <div class="spirit-nav"><a accesskey="n" href="sort/single_thread.html"><img src="../../../../doc/src/images/next.png" alt="Next"></a></div>
  21 <div class="chapter">
  22 <div class="titlepage"><div>
  23 <div><h2 class="title">
  24 <a name="sort"></a>Boost.Sort</h2></div>
  25 <div><div class="author"><h3 class="author">
  26 <span class="firstname">Steven</span> <span class="surname">Ross</span>
  27 </h3></div></div>
  28 <div><div class="author"><h3 class="author">
  29 <span class="firstname">Francisco</span> <span class="surname">Tapia</span>
  30 </h3></div></div>
  31 <div><div class="author"><h3 class="author">
  32 <span class="firstname">Orson</span> <span class="surname">Peters</span>
  33 </h3></div></div>
  34 <div><p class="copyright">Copyright &#169; 2014-2017 Steven
  35       Ross, Francisco Tapia, Orson Peters</p></div>
  36 <div><div class="legalnotice">
  37 <a name="sort.legal"></a><p>
  38         Distributed under the <a href="http://boost.org/LICENSE_1_0.txt" target="_top">Boost
  39         Software License, Version 1.0</a>.
  40       </p>
  41 </div></div>
  42 </div></div>
  43 <div class="toc">
  44 <p><b>Table of Contents</b></p>
  45 <dl class="toc">
  46 <dt><span class="section"><a href="index.html#sort.introduction">1.- Introduction</a></span></dt>
  47 <dt><span class="section"><a href="sort/single_thread.html">2.- Single Thread Algorithms</a></span></dt>
  48 <dd><dl>
  49 <dt><span class="section"><a href="sort/single_thread.html#sort.single_thread.overview">2.0.- Overview</a></span></dt>
  50 <dt><span class="section"><a href="sort/single_thread/spreadsort.html">2.1.-Spreadsort</a></span></dt>
  51 <dd><dl>
  52 <dt><span class="section"><a href="sort/single_thread/spreadsort.html#sort.single_thread.spreadsort.overview">Overview</a></span></dt>
  53 <dd><dl>
  54 <dt><span class="section"><a href="sort/single_thread/spreadsort.html#sort.single_thread.spreadsort.overview.intro">Introduction</a></span></dt>
  55 <dt><span class="section"><a href="sort/single_thread/spreadsort.html#sort.single_thread.spreadsort.overview.overloading">Overloading</a></span></dt>
  56 <dt><span class="section"><a href="sort/single_thread/spreadsort.html#sort.single_thread.spreadsort.overview.performance">Performance</a></span></dt>
  57 <dt><span class="section"><a href="sort/single_thread/spreadsort.html#sort.single_thread.spreadsort.overview.tuning">Tuning</a></span></dt>
  58 </dl></dd>
  59 <dt><span class="section"><a href="sort/single_thread/spreadsort/sort_hpp.html">Spreadsort</a></span></dt>
  60 <dd><dl>
  61 <dt><span class="section"><a href="sort/single_thread/spreadsort/sort_hpp.html#sort.single_thread.spreadsort.sort_hpp.header_spreadsort">Header
  62           <code class="computeroutput">&lt;boost/sort/spreadsort/spreadsort.hpp&gt;</code></a></span></dt>
  63 <dt><span class="section"><a href="sort/single_thread/spreadsort/sort_hpp/integer_sort.html">Integer
  64           Sort</a></span></dt>
  65 <dt><span class="section"><a href="sort/single_thread/spreadsort/sort_hpp/float_sort.html">Float
  66           Sort</a></span></dt>
  67 <dt><span class="section"><a href="sort/single_thread/spreadsort/sort_hpp/string_sort.html">String
  68           Sort</a></span></dt>
  69 <dt><span class="section"><a href="sort/single_thread/spreadsort/sort_hpp/rationale.html">Rationale</a></span></dt>
  70 </dl></dd>
  71 <dt><span class="section"><a href="sort/single_thread/spreadsort/definitions.html">Definitions</a></span></dt>
  72 <dt><span class="section"><a href="sort/single_thread/spreadsort/faq.html">Frequently Asked
  73         Questions</a></span></dt>
  74 <dt><span class="section"><a href="sort/single_thread/spreadsort/acks.html">Acknowledgements</a></span></dt>
  75 <dt><span class="section"><a href="sort/single_thread/spreadsort/bibliog.html">Bibliography</a></span></dt>
  76 <dt><span class="section"><a href="sort/single_thread/spreadsort/history.html">History</a></span></dt>
  77 <dt><span class="section"><a href="boost_sort_c___reference.html">Boost.Sort C++ Reference</a></span></dt>
  78 <dd><dl>
  79 <dt><span class="section"><a href="boost_sort_c___reference.html#header.boost.sort.spreadsort.float_sort_hpp">Header &lt;boost/sort/spreadsort/float_sort.hpp&gt;</a></span></dt>
  80 <dt><span class="section"><a href="header/boost/sort/spreadsort/integer_sort_hpp.html">Header &lt;boost/sort/spreadsort/integer_sort.hpp&gt;</a></span></dt>
  81 <dt><span class="section"><a href="header/boost/sort/spreadsort/spreadsort_hpp.html">Header &lt;boost/sort/spreadsort/spreadsort.hpp&gt;</a></span></dt>
  82 <dt><span class="section"><a href="header/boost/sort/spreadsort/string_sort_hpp.html">Header &lt;boost/sort/spreadsort/string_sort.hpp&gt;</a></span></dt>
  83 </dl></dd>
  84 </dl></dd>
  85 <dt><span class="section"><a href="sort/single_thread/pdqsort.html">2.2.- pdqsort</a></span></dt>
  86 <dd><dl>
  87 <dt><span class="section"><a href="sort/single_thread/pdqsort.html#sort.single_thread.pdqsort.pdqsort_intro">Introduction</a></span></dt>
  88 <dt><span class="section"><a href="sort/single_thread/pdqsort/pdqsort_usage.html">Usage</a></span></dt>
  89 <dt><span class="section"><a href="sort/single_thread/pdqsort/pdqsort_benchmark.html">Benchmark</a></span></dt>
  90 <dt><span class="section"><a href="sort/single_thread/pdqsort/pdqsort_best.html">The Best Case</a></span></dt>
  91 <dt><span class="section"><a href="sort/single_thread/pdqsort/pdqsort_avg.html">The Average
  92         Case</a></span></dt>
  93 <dt><span class="section"><a href="sort/single_thread/pdqsort/pdqsort_worst.html">The Worst
  94         Case</a></span></dt>
  95 <dt><span class="section"><a href="sort/single_thread/pdqsort/pdqsort_bad_partitions.html">Bad
  96         Partitions</a></span></dt>
  97 </dl></dd>
  98 <dt><span class="section"><a href="sort/single_thread/spinsort.html">2.3.- spinsort</a></span></dt>
  99 <dd><dl>
 100 <dt><span class="section"><a href="sort/single_thread/spinsort.html#sort.single_thread.spinsort.spinsort_description">Description</a></span></dt>
 101 <dt><span class="section"><a href="sort/single_thread/spinsort/spinsort_benchmark.html">Benchmark</a></span></dt>
 102 <dt><span class="section"><a href="sort/single_thread/spinsort/spinsort_programming.html">Programming</a></span></dt>
 103 </dl></dd>
 104 <dt><span class="section"><a href="sort/single_thread/flat_stable_sort.html">2.4.- flat_stable_sort</a></span></dt>
 105 <dd><dl>
 106 <dt><span class="section"><a href="sort/single_thread/flat_stable_sort.html#sort.single_thread.flat_stable_sort.flat_stable_sort_description">Description</a></span></dt>
 107 <dt><span class="section"><a href="sort/single_thread/flat_stable_sort/flat_stable_sort_benchmark.html">Benchmark</a></span></dt>
 108 <dt><span class="section"><a href="sort/single_thread/flat_stable_sort/flat_stable_sort_programming.html">Programming</a></span></dt>
 109 </dl></dd>
 110 <dt><span class="section"><a href="sort/single_thread/linux_single.html">2.5.- Linux Benchmarks</a></span></dt>
 111 <dd><dl>
 112 <dt><span class="section"><a href="sort/single_thread/linux_single.html#sort.single_thread.linux_single.near_sorted">Near Sorted
 113         Data</a></span></dt>
 114 <dt><span class="section"><a href="sort/single_thread/linux_single/complex_benchmarks.html">Complex
 115         (Several Types)</a></span></dt>
 116 </dl></dd>
 117 <dt><span class="section"><a href="sort/single_thread/windows_single.html">2.6.- Windows Benchmarks</a></span></dt>
 118 <dd><dl>
 119 <dt><span class="section"><a href="sort/single_thread/windows_single.html#sort.single_thread.windows_single.near_sorted">Near
 120         Sorted Data</a></span></dt>
 121 <dt><span class="section"><a href="sort/single_thread/windows_single/complex_benchmarks.html">Complex
 122         (Several Types)</a></span></dt>
 123 </dl></dd>
 124 </dl></dd>
 125 <dt><span class="section"><a href="sort/parallel.html">3.- Parallel Algorithms</a></span></dt>
 126 <dd><dl>
 127 <dt><span class="section"><a href="sort/parallel.html#sort.parallel.block_indirect_sort">3.1- block_indirect_sort</a></span></dt>
 128 <dd><dl>
 129 <dt><span class="section"><a href="sort/parallel.html#sort.parallel.block_indirect_sort.block_description">Description</a></span></dt>
 130 <dt><span class="section"><a href="sort/parallel.html#sort.parallel.block_indirect_sort.block_benchmark">Benchmark</a></span></dt>
 131 <dt><span class="section"><a href="sort/parallel.html#sort.parallel.block_indirect_sort.block_programming">Programming</a></span></dt>
 132 <dt><span class="section"><a href="sort/parallel.html#sort.parallel.block_indirect_sort.block_internal">Internal
 133         Description</a></span></dt>
 134 <dt><span class="section"><a href="sort/parallel.html#sort.parallel.block_indirect_sort.design_process">Design
 135         Process</a></span></dt>
 136 </dl></dd>
 137 <dt><span class="section"><a href="sort/parallel/sample_sort.html">3.2.- Sample_Sort</a></span></dt>
 138 <dd><dl>
 139 <dt><span class="section"><a href="sort/parallel/sample_sort.html#sort.parallel.sample_sort.sample_description">Description</a></span></dt>
 140 <dt><span class="section"><a href="sort/parallel/sample_sort/sample_programming.html">Programming</a></span></dt>
 141 </dl></dd>
 142 <dt><span class="section"><a href="sort/parallel/parallel_stable_sort.html">3.3.- Parallel_stable_sort</a></span></dt>
 143 <dd><dl>
 144 <dt><span class="section"><a href="sort/parallel/parallel_stable_sort.html#sort.parallel.parallel_stable_sort.parallel_description">Description</a></span></dt>
 145 <dt><span class="section"><a href="sort/parallel/parallel_stable_sort/parallel_programming.html">Programming</a></span></dt>
 146 </dl></dd>
 147 <dt><span class="section"><a href="sort/parallel/linux_parallel.html">3.4- Linux Benchmarks</a></span></dt>
 148 <dt><span class="section"><a href="sort/parallel/windows_parallel.html">3.5- Windows Benchmark</a></span></dt>
 149 </dl></dd>
 150 <dt><span class="section"><a href="sort/bibliography.html">4.- Bibliography</a></span></dt>
 151 <dt><span class="section"><a href="sort/gratitude.html">5.- Gratitude</a></span></dt>
 152 </dl>
 153 </div>
 154 <div class="section">
 155 <div class="titlepage"><div><div><h2 class="title" style="clear: both">
 156 <a name="sort.introduction"></a><a class="link" href="index.html#sort.introduction" title="1.- Introduction">1.- Introduction</a>
 157 </h2></div></div></div>
 158 <div class="blockquote"><blockquote class="blockquote">
 159 <p>
 160         The goal of the Boost Sort Library is provide to the users, the most modern,
 161         fast, and memory-efficient sorting algorithms.
 162       </p>
 163 <p>
 164         This library provides stable and unstable sorting algorithms, in single threaded
 165         and parallel versions.
 166       </p>
 167 <p>
 168         These algorithms do not use any other library or utility. The parallel algorithms
 169         need a C++11 compliant compiler.
 170       </p>
 171 <h5>
 172 <a name="sort.introduction.h0"></a>
 173         <span class="phrase"><a name="sort.introduction.single_thread_algorithms"></a></span><a class="link" href="index.html#sort.introduction.single_thread_algorithms"><span class="underline">Single Thread Algorithms</span></a>
 174       </h5>
 175 <p>
 176         <span class="bold"><strong>
 177 <pre class="programlisting">                  |       |                            |                                            | Comparison          |
 178 Algorithm         |Stable |   Additional memory        |Best, average, and worst case               | method              |
 179 ------------------+-------+----------------------------+--------------------------------------------+---------------------+
 180 spreadsort        |  no   |      key_length            | N, N sqrt(LogN), min(N logN, N key_length) | Hybrid radix sort   |
 181 pdqsort           |  no   |      Log N                 | N, N LogN, N LogN                          | Comparison operator |
 182 spinsort          |  yes  |      N / 2                 | N, N LogN, N LogN                          | Comparison operator |
 183 flat_stable_sort  |  yes  |size of the data / 256 + 8K | N, N LogN, N LogN                          | Comparison operator |
 184                   |       |                            |                                            |                     |
 185 </pre>
 186         </strong></span>
 187       </p>
 188 <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
 189 <li class="listitem">
 190             <span class="bold"><strong>spreadsort</strong></span> is an extremely fast hybrid
 191             radix sort algorithm, designed and developed by Steven Ross.
 192           </li>
 193 <li class="listitem">
 194             <span class="bold"><strong>pdqsort</strong></span> is a improvement of the quick
 195             sort algorithm, designed and developed by Orson Peters.
 196           </li>
 197 <li class="listitem">
 198             <span class="bold"><strong>spinsort</strong></span> is a stable sort that is fast
 199             with random or nearly sorted data, designed and developed by Francisco
 200             Tapia.
 201           </li>
 202 <li class="listitem">
 203             <span class="bold"><strong>flat_stable_sort</strong></span> is a stable sort that
 204             uses very little additional memory (around 1% of the size of the data),
 205             providing 80% - 90% of the speed of spinsort, designed and developed
 206             by Francisco Tapia.
 207           </li>
 208 </ul></div>
 209 <h5>
 210 <a name="sort.introduction.h1"></a>
 211         <span class="phrase"><a name="sort.introduction.parallel_algorithms"></a></span><a class="link" href="index.html#sort.introduction.parallel_algorithms"><span class="underline">Parallel Algorithms</span></a>
 212       </h5>
 213 <p>
 214         <span class="bold"><strong>
 215 <pre class="programlisting">                      |       |                        |                              |
 216 Algorithm             |Stable |   Additional memory    |Best, average, and worst case |
 217 ----------------------+-------+------------------------+------------------------------+
 218 block_indirect_sort   |  no   |block_size * num_threads| N, N LogN , N LogN           |
 219 sample_sort           |  yes  |        N               | N, N LogN , N LogN           |
 220 parallel_stable_sort  |  yes  |      N / 2             | N, N LogN , N LogN           |
 221                       |       |                        |                              |
 222 </pre>
 223         </strong></span>
 224       </p>
 225 <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
 226 <li class="listitem">
 227             <span class="bold"><strong>Sample_sort</strong></span> is a implementation of the
 228             <span class="bold"><strong><a href="https://en.wikipedia.org/wiki/Samplesort" target="_top">Samplesort
 229             algorithm</a></strong></span> done by Francisco Tapia.
 230           </li>
 231 <li class="listitem">
 232             <span class="bold"><strong>Parallel_stable_sort</strong></span> is based on the
 233             samplesort algorithm, but using a half of the memory used by sample_sort,
 234             conceived and implemented by Francisco Tapia.
 235           </li>
 236 <li class="listitem">
 237             <span class="bold"><strong>Block_indirect_sort</strong></span> is a novel high-speed
 238             parallel sort algorithm with low additional memory consumption, conceived
 239             and implemented by Francisco Tapia.
 240           </li>
 241 </ul></div>
 242 <p>
 243         The <span class="bold"><strong>block_size</strong></span> is an internal parameter
 244         of the algorithm, which in order to achieve the highest speed, changes according
 245         to the size of the objects to sort according to the next table. The strings
 246         use a block_size of 128.
 247       </p>
 248 <p>
 249         <span class="bold"><strong>
 250 <pre class="programlisting">                                |        |         |         |         |         |         |          |
 251 object size (bytes)             | 1 - 15 | 16 - 31 | 32 - 63 | 64 - 127|128 - 255|256 - 511| 512 -    |
 252 --------------------------------+--------+---------+---------+---------+---------+---------+----------+
 253 block_size (number of elements) |  4096  |  2048   |   1024  |   768   |   512   |   256   |  128     |
 254                                 |        |         |         |         |         |         |          |
 255 </pre>
 256         </strong></span>
 257       </p>
 258 </blockquote></div>
 259 </div>
 260 </div>
 261 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
 262 <td align="left"><p><small>Last revised: December 10, 2019 at 00:22:01 GMT</small></p></td>
 263 <td align="right"><div class="copyright-footer"></div></td>
 264 </tr></table>
 265 <hr>
 266 <div class="spirit-nav"><a accesskey="n" href="sort/single_thread.html"><img src="../../../../doc/src/images/next.png" alt="Next"></a></div>
 267 </body>
 268 </html>