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