1[/===========================================================================
2 Copyright (c) 2017 Steven Ross, Francisco Tapia, Orson Peters
3
4
5 Distributed under the Boost Software License, Version 1.0
6 See accompanying file LICENSE_1_0.txt or copy at
7 http://www.boost.org/LICENSE_1_0.txt
8=============================================================================/]
9
10
11[section:spinsort 2.3.- spinsort]
12
13
14[section:spinsort_description Description]
15[:
16
17[*Spinsort] is a new stable sort algorithm, designed and implemented by Francisco Tapia for the Boost Sort Library.
18
19This algorithm combines several ideas used to optimize other stable sort algorithms.
20
21
22[*[teletype]
23``
24                |         |                   |                                |
25    Algorithm   | Stable  | Additional Memory | Best, average, and worst case  |
26    ------------+---------+-------------------+--------------------------------+
27    spinsort    |   Yes   |      N / 2        |     N, NlogN , NlogN           |
28                |         |                   |                                |
29
30``
31]
32
33The algorithm is most efficient when the data are nearly sorted.  Many times the new elements are inserted at the end
34of the sorted elements, or some elements are modified, breaking the order of the elements. In these cases, spinsort
35is very fast.
36
37]
38[endsect] [/section:spinsort_description Description]
39
40[section:spinsort_benchmark Benchmark]
41[:
42
43The 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 .
44
45
46[*[teletype]
47``
48    Data                           |std::stable_sort |   spin_sort  |
49    -------------------------------+-----------------+--------------+
50    random                         |     8.62        |     9.73     |
51                                   |                 |              |
52    sorted                         |     4.88        |     0.06     |
53    sorted + 0.1% end              |     4.92        |     0.41     |
54    sorted +   1% end              |     4.97        |     0.55     |
55    sorted +  10% end              |     5.73        |     1.32     |
56                                   |                 |              |
57    sorted + 0.1% middle           |     6.58        |     1.89     |
58    sorted +   1% middle           |     7.06        |     2.12     |
59    sorted +  10% middle           |     9.56        |     4.02     |
60                                   |                 |              |
61    reverse sorted                 |     0.13        |     0.14     |
62    reverse sorted + 0.1% end      |     5.22        |     0.52     |
63    reverse sorted +   1% end      |     5.29        |     0.66     |
64    reverse sorted +  10% end      |     6.03        |     1.45     |
65                                   |                 |              |
66    reverse sorted + 0.1% middle   |     6.52        |     1.89     |
67    reverse sorted +   1% middle   |     7.09        |     2.12     |
68    reverse sorted +  10% middle   |     9.46        |     4.02     |
69                                   |                 |              |
70    -------------------------------+-----------------+--------------+
71``
72]
73]
74[endsect] [/section:spinsort_benchmark Benchmark]
75[section:spinsort_programming Programming]
76
77[:
78You only need to include the file boost/sort/sort.hpp to use spinsort.
79
80The spinsort function is in the namespace boost::sort
81
82[c++]
83``
84
85    #include <boost/sort/sort.hpp>
86
87
88    template <class iter_t,  typename compare>
89    void spinsort (iter_t first, iter_t last, compare comp = compare());
90
91``
92
93This algorithm uses a [*comparison object], in the same way as the standard library sort
94algorithms. If you don't define it, the comparison object defaults to std::less, which uses
95the < operator internally for comparisons.
96
97This algorithm is [*exception safe],  meaning that, the exceptions generated by the algorithm
98guarantee the integrity of the objects to sort, but not their relative order. If the exception
99is generated inside the objects (in the move or copy constructors) the results are undefined.
100]
101[endsect] [/section:spinsort_programming Programming]
102[endsect]
103