1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
[/===========================================================================
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:single_thread 2.- Single Thread Algorithms]
[section:overview 2.0.- Overview]
[:
[h4[_Single Thread Algorithms]]
[:
This table provides a brief description of the single thread algorithms of the library.
[*[teletype]
``
| | | | Comparison |
Algorithm |Stable | Additional memory | Best, average, and worst case | method |
------------------+-------+----------------------------+-----------------------------------------+---------------------+
spreadsort | no | key_length | N, Nsqrt(LogN), min(NlogN, Nkey_length) | Hybrid radix sort |
pdqsort | no | Log N | N, NLogN, NLogN | Comparison operator |
spinsort | yes | N / 2 | N, NLogN, NLogN | Comparison operator |
flat_stable_sort | yes |size of the data / 256 + 8K | N, NLogN, NLogN | 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.
]
]
[endsect]
[include spreadsort.qbk]
[include pdqsort.qbk]
[include spinsort.qbk]
[include flat_stable_sort.qbk]
[include linux_single.qbk]
[include windows_single.qbk]
[endsect]
|
