devn00b
/
EQ2EMu


			
				
					
						
						
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268
							<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Boost.Sort</title>
<link rel="stylesheet" href="../../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="index.html" title="Boost.Sort">
<link rel="next" href="sort/single_thread.html" title="2.- Single Thread Algorithms">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../boost.png"></td>
<td align="center"><a href="../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav"><a accesskey="n" href="sort/single_thread.html"><img src="../../../../doc/src/images/next.png" alt="Next"></a></div>
<div class="chapter">
<div class="titlepage"><div>
<div><h2 class="title">
<a name="sort"></a>Boost.Sort</h2></div>
<div><div class="author"><h3 class="author">
<span class="firstname">Steven</span> <span class="surname">Ross</span>
</h3></div></div>
<div><div class="author"><h3 class="author">
<span class="firstname">Francisco</span> <span class="surname">Tapia</span>
</h3></div></div>
<div><div class="author"><h3 class="author">
<span class="firstname">Orson</span> <span class="surname">Peters</span>
</h3></div></div>
<div><p class="copyright">Copyright &#169; 2014-2017 Steven
      Ross, Francisco Tapia, Orson Peters</p></div>
<div><div class="legalnotice">
<a name="sort.legal"></a><p>
        Distributed under the <a href="http://boost.org/LICENSE_1_0.txt" target="_top">Boost
        Software License, Version 1.0</a>.
      </p>
</div></div>
</div></div>
<div class="toc">
<p><b>Table of Contents</b></p>
<dl class="toc">
<dt><span class="section"><a href="index.html#sort.introduction">1.- Introduction</a></span></dt>
<dt><span class="section"><a href="sort/single_thread.html">2.- Single Thread Algorithms</a></span></dt>
<dd><dl>
<dt><span class="section"><a href="sort/single_thread.html#sort.single_thread.overview">2.0.- Overview</a></span></dt>
<dt><span class="section"><a href="sort/single_thread/spreadsort.html">2.1.-Spreadsort</a></span></dt>
<dd><dl>
<dt><span class="section"><a href="sort/single_thread/spreadsort.html#sort.single_thread.spreadsort.overview">Overview</a></span></dt>
<dd><dl>
<dt><span class="section"><a href="sort/single_thread/spreadsort.html#sort.single_thread.spreadsort.overview.intro">Introduction</a></span></dt>
<dt><span class="section"><a href="sort/single_thread/spreadsort.html#sort.single_thread.spreadsort.overview.overloading">Overloading</a></span></dt>
<dt><span class="section"><a href="sort/single_thread/spreadsort.html#sort.single_thread.spreadsort.overview.performance">Performance</a></span></dt>
<dt><span class="section"><a href="sort/single_thread/spreadsort.html#sort.single_thread.spreadsort.overview.tuning">Tuning</a></span></dt>
</dl></dd>
<dt><span class="section"><a href="sort/single_thread/spreadsort/sort_hpp.html">Spreadsort</a></span></dt>
<dd><dl>
<dt><span class="section"><a href="sort/single_thread/spreadsort/sort_hpp.html#sort.single_thread.spreadsort.sort_hpp.header_spreadsort">Header
          <code class="computeroutput">&lt;boost/sort/spreadsort/spreadsort.hpp&gt;</code></a></span></dt>
<dt><span class="section"><a href="sort/single_thread/spreadsort/sort_hpp/integer_sort.html">Integer
          Sort</a></span></dt>
<dt><span class="section"><a href="sort/single_thread/spreadsort/sort_hpp/float_sort.html">Float
          Sort</a></span></dt>
<dt><span class="section"><a href="sort/single_thread/spreadsort/sort_hpp/string_sort.html">String
          Sort</a></span></dt>
<dt><span class="section"><a href="sort/single_thread/spreadsort/sort_hpp/rationale.html">Rationale</a></span></dt>
</dl></dd>
<dt><span class="section"><a href="sort/single_thread/spreadsort/definitions.html">Definitions</a></span></dt>
<dt><span class="section"><a href="sort/single_thread/spreadsort/faq.html">Frequently Asked
        Questions</a></span></dt>
<dt><span class="section"><a href="sort/single_thread/spreadsort/acks.html">Acknowledgements</a></span></dt>
<dt><span class="section"><a href="sort/single_thread/spreadsort/bibliog.html">Bibliography</a></span></dt>
<dt><span class="section"><a href="sort/single_thread/spreadsort/history.html">History</a></span></dt>
<dt><span class="section"><a href="boost_sort_c___reference.html">Boost.Sort C++ Reference</a></span></dt>
<dd><dl>
<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>
<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>
<dt><span class="section"><a href="header/boost/sort/spreadsort/spreadsort_hpp.html">Header &lt;boost/sort/spreadsort/spreadsort.hpp&gt;</a></span></dt>
<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>
</dl></dd>
</dl></dd>
<dt><span class="section"><a href="sort/single_thread/pdqsort.html">2.2.- pdqsort</a></span></dt>
<dd><dl>
<dt><span class="section"><a href="sort/single_thread/pdqsort.html#sort.single_thread.pdqsort.pdqsort_intro">Introduction</a></span></dt>
<dt><span class="section"><a href="sort/single_thread/pdqsort/pdqsort_usage.html">Usage</a></span></dt>
<dt><span class="section"><a href="sort/single_thread/pdqsort/pdqsort_benchmark.html">Benchmark</a></span></dt>
<dt><span class="section"><a href="sort/single_thread/pdqsort/pdqsort_best.html">The Best Case</a></span></dt>
<dt><span class="section"><a href="sort/single_thread/pdqsort/pdqsort_avg.html">The Average
        Case</a></span></dt>
<dt><span class="section"><a href="sort/single_thread/pdqsort/pdqsort_worst.html">The Worst
        Case</a></span></dt>
<dt><span class="section"><a href="sort/single_thread/pdqsort/pdqsort_bad_partitions.html">Bad
        Partitions</a></span></dt>
</dl></dd>
<dt><span class="section"><a href="sort/single_thread/spinsort.html">2.3.- spinsort</a></span></dt>
<dd><dl>
<dt><span class="section"><a href="sort/single_thread/spinsort.html#sort.single_thread.spinsort.spinsort_description">Description</a></span></dt>
<dt><span class="section"><a href="sort/single_thread/spinsort/spinsort_benchmark.html">Benchmark</a></span></dt>
<dt><span class="section"><a href="sort/single_thread/spinsort/spinsort_programming.html">Programming</a></span></dt>
</dl></dd>
<dt><span class="section"><a href="sort/single_thread/flat_stable_sort.html">2.4.- flat_stable_sort</a></span></dt>
<dd><dl>
<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>
<dt><span class="section"><a href="sort/single_thread/flat_stable_sort/flat_stable_sort_benchmark.html">Benchmark</a></span></dt>
<dt><span class="section"><a href="sort/single_thread/flat_stable_sort/flat_stable_sort_programming.html">Programming</a></span></dt>
</dl></dd>
<dt><span class="section"><a href="sort/single_thread/linux_single.html">2.5.- Linux Benchmarks</a></span></dt>
<dd><dl>
<dt><span class="section"><a href="sort/single_thread/linux_single.html#sort.single_thread.linux_single.near_sorted">Near Sorted
        Data</a></span></dt>
<dt><span class="section"><a href="sort/single_thread/linux_single/complex_benchmarks.html">Complex
        (Several Types)</a></span></dt>
</dl></dd>
<dt><span class="section"><a href="sort/single_thread/windows_single.html">2.6.- Windows Benchmarks</a></span></dt>
<dd><dl>
<dt><span class="section"><a href="sort/single_thread/windows_single.html#sort.single_thread.windows_single.near_sorted">Near
        Sorted Data</a></span></dt>
<dt><span class="section"><a href="sort/single_thread/windows_single/complex_benchmarks.html">Complex
        (Several Types)</a></span></dt>
</dl></dd>
</dl></dd>
<dt><span class="section"><a href="sort/parallel.html">3.- Parallel Algorithms</a></span></dt>
<dd><dl>
<dt><span class="section"><a href="sort/parallel.html#sort.parallel.block_indirect_sort">3.1- block_indirect_sort</a></span></dt>
<dd><dl>
<dt><span class="section"><a href="sort/parallel.html#sort.parallel.block_indirect_sort.block_description">Description</a></span></dt>
<dt><span class="section"><a href="sort/parallel.html#sort.parallel.block_indirect_sort.block_benchmark">Benchmark</a></span></dt>
<dt><span class="section"><a href="sort/parallel.html#sort.parallel.block_indirect_sort.block_programming">Programming</a></span></dt>
<dt><span class="section"><a href="sort/parallel.html#sort.parallel.block_indirect_sort.block_internal">Internal
        Description</a></span></dt>
<dt><span class="section"><a href="sort/parallel.html#sort.parallel.block_indirect_sort.design_process">Design
        Process</a></span></dt>
</dl></dd>
<dt><span class="section"><a href="sort/parallel/sample_sort.html">3.2.- Sample_Sort</a></span></dt>
<dd><dl>
<dt><span class="section"><a href="sort/parallel/sample_sort.html#sort.parallel.sample_sort.sample_description">Description</a></span></dt>
<dt><span class="section"><a href="sort/parallel/sample_sort/sample_programming.html">Programming</a></span></dt>
</dl></dd>
<dt><span class="section"><a href="sort/parallel/parallel_stable_sort.html">3.3.- Parallel_stable_sort</a></span></dt>
<dd><dl>
<dt><span class="section"><a href="sort/parallel/parallel_stable_sort.html#sort.parallel.parallel_stable_sort.parallel_description">Description</a></span></dt>
<dt><span class="section"><a href="sort/parallel/parallel_stable_sort/parallel_programming.html">Programming</a></span></dt>
</dl></dd>
<dt><span class="section"><a href="sort/parallel/linux_parallel.html">3.4- Linux Benchmarks</a></span></dt>
<dt><span class="section"><a href="sort/parallel/windows_parallel.html">3.5- Windows Benchmark</a></span></dt>
</dl></dd>
<dt><span class="section"><a href="sort/bibliography.html">4.- Bibliography</a></span></dt>
<dt><span class="section"><a href="sort/gratitude.html">5.- Gratitude</a></span></dt>
</dl>
</div>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="sort.introduction"></a><a class="link" href="index.html#sort.introduction" title="1.- Introduction">1.- Introduction</a>
</h2></div></div></div>
<div class="blockquote"><blockquote class="blockquote">
<p>
        The goal of the Boost Sort Library is provide to the users, the most modern,
        fast, and memory-efficient sorting algorithms.
      </p>
<p>
        This library provides stable and unstable sorting algorithms, in single threaded
        and parallel versions.
      </p>
<p>
        These algorithms do not use any other library or utility. The parallel algorithms
        need a C++11 compliant compiler.
      </p>
<h5>
<a name="sort.introduction.h0"></a>
        <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>
      </h5>
<p>
        <span class="bold"><strong>
<pre class="programlisting">                  |       |                            |                                            | Comparison          |
Algorithm         |Stable |   Additional memory        |Best, average, and worst case               | method              |
------------------+-------+----------------------------+--------------------------------------------+---------------------+
spreadsort        |  no   |      key_length            | N, N sqrt(LogN), min(N logN, N key_length) | Hybrid radix sort   |
pdqsort           |  no   |      Log N                 | N, N LogN, N LogN                          | Comparison operator |
spinsort          |  yes  |      N / 2                 | N, N LogN, N LogN                          | Comparison operator |
flat_stable_sort  |  yes  |size of the data / 256 + 8K | N, N LogN, N LogN                          | Comparison operator |
                  |       |                            |                                            |                     |
</pre>
        </strong></span>
      </p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
            <span class="bold"><strong>spreadsort</strong></span> is an extremely fast hybrid
            radix sort algorithm, designed and developed by Steven Ross.
          </li>
<li class="listitem">
            <span class="bold"><strong>pdqsort</strong></span> is a improvement of the quick
            sort algorithm, designed and developed by Orson Peters.
          </li>
<li class="listitem">
            <span class="bold"><strong>spinsort</strong></span> is a stable sort that is fast
            with random or nearly sorted data, designed and developed by Francisco
            Tapia.
          </li>
<li class="listitem">
            <span class="bold"><strong>flat_stable_sort</strong></span> is a stable sort that
            uses very little additional memory (around 1% of the size of the data),
            providing 80% - 90% of the speed of spinsort, designed and developed
            by Francisco Tapia.
          </li>
</ul></div>
<h5>
<a name="sort.introduction.h1"></a>
        <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>
      </h5>
<p>
        <span class="bold"><strong>
<pre class="programlisting">                      |       |                        |                              |
Algorithm             |Stable |   Additional memory    |Best, average, and worst case |
----------------------+-------+------------------------+------------------------------+
block_indirect_sort   |  no   |block_size * num_threads| N, N LogN , N LogN           |
sample_sort           |  yes  |        N               | N, N LogN , N LogN           |
parallel_stable_sort  |  yes  |      N / 2             | N, N LogN , N LogN           |
                      |       |                        |                              |
</pre>
        </strong></span>
      </p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
            <span class="bold"><strong>Sample_sort</strong></span> is a implementation of the
            <span class="bold"><strong><a href="https://en.wikipedia.org/wiki/Samplesort" target="_top">Samplesort
            algorithm</a></strong></span> done by Francisco Tapia.
          </li>
<li class="listitem">
            <span class="bold"><strong>Parallel_stable_sort</strong></span> is based on the
            samplesort algorithm, but using a half of the memory used by sample_sort,
            conceived and implemented by Francisco Tapia.
          </li>
<li class="listitem">
            <span class="bold"><strong>Block_indirect_sort</strong></span> is a novel high-speed
            parallel sort algorithm with low additional memory consumption, conceived
            and implemented by Francisco Tapia.
          </li>
</ul></div>
<p>
        The <span class="bold"><strong>block_size</strong></span> is an internal parameter
        of the algorithm, which in order to achieve the highest speed, changes according
        to the size of the objects to sort according to the next table. The strings
        use a block_size of 128.
      </p>
<p>
        <span class="bold"><strong>
<pre class="programlisting">                                |        |         |         |         |         |         |          |
object size (bytes)             | 1 - 15 | 16 - 31 | 32 - 63 | 64 - 127|128 - 255|256 - 511| 512 -    |
--------------------------------+--------+---------+---------+---------+---------+---------+----------+
block_size (number of elements) |  4096  |  2048   |   1024  |   768   |   512   |   256   |  128     |
                                |        |         |         |         |         |         |          |
</pre>
        </strong></span>
      </p>
</blockquote></div>
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"><p><small>Last revised: December 10, 2019 at 00:22:01 GMT</small></p></td>
<td align="right"><div class="copyright-footer"></div></td>
</tr></table>
<hr>
<div class="spirit-nav"><a accesskey="n" href="sort/single_thread.html"><img src="../../../../doc/src/images/next.png" alt="Next"></a></div>
</body>
</html>