[/===========================================================================
 Copyright (c) 2017 Steven Ross, Francisco Tapia, Orson Peters


 Distributed under the Boost Software License, Version 1.0
 See accompanying file LICENSE_1_0.txt or copy at
 http://www.boost.org/LICENSE_1_0.txt
=============================================================================/]


[section:spinsort 2.3.- spinsort]


[section:spinsort_description Description]
[:

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


[*[teletype]
``
                |         |                   |                                |
    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.

]
[endsect] [/section:spinsort_description Description]

[section:spinsort_benchmark Benchmark]
[:

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


[*[teletype]
``
    Data                           |std::stable_sort |   spin_sort  |
    -------------------------------+-----------------+--------------+
    random                         |     8.62        |     9.73     |
                                   |                 |              |
    sorted                         |     4.88        |     0.06     |
    sorted + 0.1% end              |     4.92        |     0.41     |
    sorted +   1% end              |     4.97        |     0.55     |
    sorted +  10% end              |     5.73        |     1.32     |
                                   |                 |              |
    sorted + 0.1% middle           |     6.58        |     1.89     |
    sorted +   1% middle           |     7.06        |     2.12     |
    sorted +  10% middle           |     9.56        |     4.02     |
                                   |                 |              |
    reverse sorted                 |     0.13        |     0.14     |
    reverse sorted + 0.1% end      |     5.22        |     0.52     |
    reverse sorted +   1% end      |     5.29        |     0.66     |
    reverse sorted +  10% end      |     6.03        |     1.45     |
                                   |                 |              |
    reverse sorted + 0.1% middle   |     6.52        |     1.89     |
    reverse sorted +   1% middle   |     7.09        |     2.12     |
    reverse sorted +  10% middle   |     9.46        |     4.02     |
                                   |                 |              |
    -------------------------------+-----------------+--------------+
``
]
]
[endsect] [/section:spinsort_benchmark Benchmark]
[section:spinsort_programming Programming]

[:
You only need to include the file boost/sort/sort.hpp to use spinsort.

The spinsort function is in the namespace boost::sort

[c++]
``

    #include <boost/sort/sort.hpp>


    template <class iter_t,  typename compare>
    void spinsort (iter_t first, iter_t last, compare comp = compare());

``

This algorithm uses a [*comparison object], in the same way as the standard library sort
algorithms. If you don't define it, the comparison object defaults to std::less, which uses
the < operator internally for comparisons.

This algorithm is [*exception safe],  meaning that, the exceptions generated by the algorithm
guarantee the integrity of the objects to sort, but not their relative order. If the exception
is generated inside the objects (in the move or copy constructors) the results are undefined.
]
[endsect] [/section:spinsort_programming Programming]
[endsect]