1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 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 © 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"><boost/sort/spreadsort/spreadsort.hpp></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 <boost/sort/spreadsort/float_sort.hpp></a></span></dt> 80<dt><span class="section"><a href="header/boost/sort/spreadsort/integer_sort_hpp.html">Header <boost/sort/spreadsort/integer_sort.hpp></a></span></dt> 81<dt><span class="section"><a href="header/boost/sort/spreadsort/spreadsort_hpp.html">Header <boost/sort/spreadsort/spreadsort.hpp></a></span></dt> 82<dt><span class="section"><a href="header/boost/sort/spreadsort/string_sort_hpp.html">Header <boost/sort/spreadsort/string_sort.hpp></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 | 178Algorithm |Stable | Additional memory |Best, average, and worst case | method | 179------------------+-------+----------------------------+--------------------------------------------+---------------------+ 180spreadsort | no | key_length | N, N sqrt(LogN), min(N logN, N key_length) | Hybrid radix sort | 181pdqsort | no | Log N | N, N LogN, N LogN | Comparison operator | 182spinsort | yes | N / 2 | N, N LogN, N LogN | Comparison operator | 183flat_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"> | | | | 216Algorithm |Stable | Additional memory |Best, average, and worst case | 217----------------------+-------+------------------------+------------------------------+ 218block_indirect_sort | no |block_size * num_threads| N, N LogN , N LogN | 219sample_sort | yes | N | N, N LogN , N LogN | 220parallel_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"> | | | | | | | | 251object size (bytes) | 1 - 15 | 16 - 31 | 32 - 63 | 64 - 127|128 - 255|256 - 511| 512 - | 252--------------------------------+--------+---------+---------+---------+---------+---------+----------+ 253block_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: August 11, 2020 at 14:59:33 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> 269
