56 lines
2.3 KiB
Plaintext
56 lines
2.3 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: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]
|
|
|
|
|
|
|