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