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:single_thread 2.- Single Thread Algorithms]
11[section:overview 2.0.- Overview]
12[:
13
14[h4[_Single Thread Algorithms]]
15
16[:
17This table provides a brief description of the single thread algorithms of the library.
18
19
20[*[teletype]
21``
22                      |       |                            |                                         | Comparison          |
23    Algorithm         |Stable |   Additional memory        |  Best, average, and worst case          | method              |
24    ------------------+-------+----------------------------+-----------------------------------------+---------------------+
25    spreadsort        |  no   |      key_length            | N, Nsqrt(LogN), min(NlogN, Nkey_length) | Hybrid radix sort   |
26    pdqsort           |  no   |      Log N                 | N, NLogN, NLogN                         | Comparison operator |
27    spinsort          |  yes  |      N / 2                 | N, NLogN, NLogN                         | Comparison operator |
28    flat_stable_sort  |  yes  |size of the data / 256 + 8K | N, NLogN, NLogN                         | Comparison operator |
29                      |       |                            |                                         |                     |
30``
31]
32
33* *spreadsort* is an extremely fast hybrid radix sort algorithm, designed and developed by Steven Ross.
34
35* *pdqsort* is a improvement of the quick sort algorithm, designed and developed by Orson Peters.
36
37* *spinsort* is a stable sort that is fast with random or nearly sorted data, designed and developed by Francisco Tapia.
38
39* *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
40 spinsort, designed and developed by Francisco Tapia.
41
42]
43
44]
45[endsect]
46[include spreadsort.qbk]
47[include pdqsort.qbk]
48[include spinsort.qbk]
49[include flat_stable_sort.qbk]
50[include linux_single.qbk]
51[include windows_single.qbk]
52[endsect]
53
54
55
56