Boost
C++ Libraries
...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
Single Thread Algorithms
This table provides a brief description of the single thread algorithms of the library.
| | | | 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.