Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world.

2.0.- Overview
Overview
Introduction
Performance
Tuning
Header `<boost/sort/spreadsort/spreadsort.hpp>`
Integer Sort
Integer Sort Examples
Float Sort
Float Sort Examples
String Sort
String Sort Examples
Rationale
Unstable Sorting
Unused X86 optimization
Lookup Table?
Definitions
Acknowledgements
Bibliography
History
Boost.Sort C++ Reference
2.2.- pdqsort
Introduction
Usage
Benchmark
The Best Case
The Average Case
The Worst Case
2.3.- spinsort
Description
Benchmark
Programming
2.4.- flat_stable_sort
Description
Benchmark
Programming
2.5.- Linux Benchmarks
Near Sorted Data
Complex (Several Types)
2.6.- Windows Benchmarks
Near Sorted Data
Complex (Several Types)

2.0.- Overview

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.