1[/=========================================================================== 2 Copyright (c) 2017 Steven Ross, Francisco Tapia, Orson Peters 3 4 5 Distributed under the Boost Software License, Version 1.0 6 See accompanying file LICENSE_1_0.txt or copy at 7 http://www.boost.org/LICENSE_1_0.txt 8=============================================================================/] 9 10[section:introduction 1.- Introduction] 11 12[: 13The goal of the Boost Sort Library is provide to the users, the most modern, fast, and memory-efficient sorting algorithms. 14 15This library provides stable and unstable sorting algorithms, in single threaded and parallel versions. 16 17These algorithms do not use any other library or utility. The parallel algorithms need a C++11 compliant compiler. 18 19[h4[_Single Thread Algorithms]] 20 21 22[*[teletype] 23`` 24 | | | | Comparison | 25 Algorithm |Stable | Additional memory |Best, average, and worst case | method | 26 ------------------+-------+----------------------------+--------------------------------------------+---------------------+ 27 spreadsort | no | key_length | N, N sqrt(LogN), min(N logN, N key_length) | Hybrid radix sort | 28 pdqsort | no | Log N | N, N LogN, N LogN | Comparison operator | 29 spinsort | yes | N / 2 | N, N LogN, N LogN | Comparison operator | 30 flat_stable_sort | yes |size of the data / 256 + 8K | N, N LogN, N LogN | Comparison operator | 31 | | | | | 32`` 33] 34 35* *spreadsort* is an extremely fast hybrid radix sort algorithm, designed and developed by Steven Ross. 36 37* *pdqsort* is a improvement of the quick sort algorithm, designed and developed by Orson Peters. 38 39* *spinsort* is a stable sort that is fast with random or nearly sorted data, designed and developed by Francisco Tapia. 40 41* *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 42 spinsort, designed and developed by Francisco Tapia. 43 44[h4[_Parallel Algorithms]] 45 46 47[*[teletype] 48`` 49 | | | | 50 Algorithm |Stable | Additional memory |Best, average, and worst case | 51 ----------------------+-------+------------------------+------------------------------+ 52 block_indirect_sort | no |block_size * num_threads| N, N LogN , N LogN | 53 sample_sort | yes | N | N, N LogN , N LogN | 54 parallel_stable_sort | yes | N / 2 | N, N LogN , N LogN | 55 | | | | 56`` 57] 58 59* *Sample_sort* is a implementation of the [*[@ https://en.wikipedia.org/wiki/Samplesort Samplesort algorithm]] done by Francisco Tapia. 60 61* *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. 62 63* *Block_indirect_sort* is a novel high-speed parallel sort algorithm with low additional memory consumption, conceived and implemented by Francisco Tapia. 64 65 66The *block_size* is an internal parameter of the algorithm, which in order to achieve the 67highest speed, changes according to the size of the objects to sort according to the next table. The strings use a block_size of 128. 68 69[*[teletype] 70`` 71 | | | | | | | | 72object size (bytes) | 1 - 15 | 16 - 31 | 32 - 63 | 64 - 127|128 - 255|256 - 511| 512 - | 73--------------------------------+--------+---------+---------+---------+---------+---------+----------+ 74block_size (number of elements) | 4096 | 2048 | 1024 | 768 | 512 | 256 | 128 | 75 | | | | | | | | 76`` 77] 78] 79 80 81 82[endsect] 83 84 85 86