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

This is the documentation for an old version of Boost. Click here to view this page for the latest version.
PrevUpHomeNext

2.4.- flat_stable_sort

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    |
-------------------+--------------+


PrevUpHomeNext