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

Benchmark

The benchmark with 100000000 64 bits integers,comparing with std::stable_sort of GCC 6.3 compiler and spinsort, running on a Intel i7-5820K CPU @ 3.30GH shows the mentioned characteristics.

Data                         |std::stable_sort| spin_sort  |flat_stable_sort |
-----------------------------+----------------+------------+-----------------+
random                       |     8.62       |    9.73    |     10.80       |
                             |                |            |                 |
sorted                       |     4.88       |    0.06    |      0.07       |
sorted + 0.1% end            |     4.92       |    0.41    |      0.36       |
sorted +   1% end            |     4.97       |    0.55    |      0.49       |
sorted +  10% end            |     5.73       |    1.32    |      1.40       |
                             |                |            |                 |
sorted + 0.1% middle         |     6.58       |    1.89    |      2.61       |
sorted +   1% middle         |     7.06       |    2.12    |      3.07       |
sorted +  10% middle         |     9.56       |    4.02    |      5.49       |
                             |                |            |                 |
reverse sorted               |     0.13       |    0.14    |      1.87       |
reverse sorted + 0.1% end    |     5.22       |    0.52    |      0.42       |
reverse sorted +   1% end    |     5.29       |    0.66    |      0.55       |
reverse sorted +  10% end    |     6.03       |    1.45    |      1.44       |
                             |                |            |                 |
reverse sorted + 0.1% middle |     6.52       |    1.89    |      2.54       |
reverse sorted +   1% middle |     7.09       |    2.12    |      3.09       |
reverse sorted +  10% middle |     9.46       |    4.02    |      5.53       |
                             |                |            |                 |
-----------------------------+----------------+------------+-----------------+

If you want detailed information about this algorithm you can find it in the flat_stable_sort_en.pdf document


PrevUpHomeNext