...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
Flat_stable_sort is a new stable sort algorithm, designed and implemented by Francisco Jose Tapia for the Boost Sort Library
The goal of the algorithm is to stably sort with little additional memory (about 1% of the memory used by the data).
The default stable sort algorithms provided by most compilers and libraries use substantial additional memory, usually half of the data to sort.
This new algorithm provides around 80%-90% of the speed of the spinsort and the stable sort algorithms provided by compilers and libraries.
This algorithm is fast when the data is almost sorted. Many times the new elements are inserted at the end of the sorted elements, or some elements are modified, breaking the order of the elements. In these cases, the flat_stable_sort algorithm is very fast.
| | | | Algorithm | Stable | Additional Memory | Best, average, and worst case | -----------------+---------+-----------------------------+--------------------------------+ flat_stable_sort | Yes | size of the data / 256 + 8K | N, NlogN , NlogN | | | | |
Memory Used
Memory used by the stable sort algorithms measured on Linux x64
Algorithm | Memory used | -------------------+--------------+ std::stable_sort | 1177 MB | spinsort | 1175 MB | flat_stable_sort | 788 MB | -------------------+--------------+