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