86 lines
4.2 KiB
Plaintext
86 lines
4.2 KiB
Plaintext
[/===========================================================================
|
|
Copyright (c) 2017 Steven Ross, Francisco Tapia, Orson Peters
|
|
|
|
|
|
Distributed under the Boost Software License, Version 1.0
|
|
See accompanying file LICENSE_1_0.txt or copy at
|
|
http://www.boost.org/LICENSE_1_0.txt
|
|
=============================================================================/]
|
|
|
|
[section:introduction 1.- Introduction]
|
|
|
|
[:
|
|
The goal of the Boost Sort Library is provide to the users, the most modern, fast, and memory-efficient sorting algorithms.
|
|
|
|
This library provides stable and unstable sorting algorithms, in single threaded and parallel versions.
|
|
|
|
These algorithms do not use any other library or utility. The parallel algorithms need a C++11 compliant compiler.
|
|
|
|
[h4[_Single Thread Algorithms]]
|
|
|
|
|
|
[*[teletype]
|
|
``
|
|
| | | | 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 |
|
|
| | | | |
|
|
``
|
|
]
|
|
|
|
* *spreadsort* is an extremely fast hybrid radix sort algorithm, designed and developed by Steven Ross.
|
|
|
|
* *pdqsort* is a improvement of the quick sort algorithm, designed and developed by Orson Peters.
|
|
|
|
* *spinsort* is a stable sort that is fast with random or nearly sorted data, designed and developed by Francisco Tapia.
|
|
|
|
* *flat_stable_sort* 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.
|
|
|
|
[h4[_Parallel Algorithms]]
|
|
|
|
|
|
[*[teletype]
|
|
``
|
|
| | | |
|
|
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 |
|
|
| | | |
|
|
``
|
|
]
|
|
|
|
* *Sample_sort* is a implementation of the [*[@ https://en.wikipedia.org/wiki/Samplesort Samplesort algorithm]] done by Francisco Tapia.
|
|
|
|
* *Parallel_stable_sort* is based on the samplesort algorithm, but using a half of the memory used by sample_sort, conceived and implemented by Francisco Tapia.
|
|
|
|
* *Block_indirect_sort* is a novel high-speed parallel sort algorithm with low additional memory consumption, conceived and implemented by Francisco Tapia.
|
|
|
|
|
|
The *block_size* 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.
|
|
|
|
[*[teletype]
|
|
``
|
|
| | | | | | | |
|
|
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 |
|
|
| | | | | | | |
|
|
``
|
|
]
|
|
]
|
|
|
|
|
|
|
|
[endsect]
|
|
|
|
|
|
|