| 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485 |
- [/===========================================================================
- 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]
|
