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 a snapshot of the develop branch, built from commit 0f79ae966a.
PrevUpHomeNext

2.3.- spinsort

Spinsort is a new stable sort algorithm, designed and implemented by Francisco Tapia for the Boost Sort Library.

This algorithm combines several ideas used to optimize other stable sort algorithms.

            |         |                   |                                |
Algorithm   | Stable  | Additional Memory | Best, average, and worst case  |
------------+---------+-------------------+--------------------------------+
spinsort    |   Yes   |      N / 2        |     N, NlogN , NlogN           |
            |         |                   |                                |

The algorithm is most efficient when the data are nearly 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, spinsort is very fast.


PrevUpHomeNext