How It Works
Sort Target
Algorithm
Speed
Normal ~12s · 37 ms ×5
Spinsort(2016)
▶ Try this Source
O(n log n) ✓ Stable ✗ In-place ✓ Adaptive

Combined with: Binary insert sort (small ranges), Insertion sort (small ranges)

🔧 How it works

A re-implementation of Boost.Sort's Spinsort. Checks for sorted or fully reversed input in O(n), then splits into two halves, sorts the left via ping-pong merge into a half-buffer, sorts the right in-place using the freed left space as scratch, and merges with a half-merge.

🎯 Key property

Uses only ceil(n/2) auxiliary memory while maintaining stability. Achieves O(n) on sorted, reversed, or nearly-sorted input. For large ranges (over 1024 elements), CheckStableSort detects a sorted prefix with a small unsorted tail and handles it via partial insertion.

👁 Watch for
  • Compare CheckPreSorted scans adjacent pairs for fully sorted or reversed input; CheckStableSort scans for a sorted prefix with a small unsorted tail in large ranges
  • Swap only occurs when reversing a fully descending input in-place
  • RangeCopy data moves between the main array and half-buffer during ping-pong merge; the half-merge reads from the buffer and in-place right portion simultaneously
🕰 History 🌳 Lineage ⚡ Optimization
UsesRun DetectionCopy-Smaller StrategySortedness DetectionHybrid SwitchingPing-Pong Buffering
Initial State
This is the array before sorting. Follow Spinsort step by step.
Main Array
73
0
79
1
63
2
8
3
29
4
31
5
27
6
78
7
67
8
6
9
37
10
51
11
7
12
24
13
5
14
33
15
25
16
56
17
75
18
32
19
1
20
60
21
59
22
36
23
46
24
41
25
47
26
61
27
57
28
20
29
70
30
38
31
66
32
44
33
53
34
43
35
17
36
49
37
77
38
26
39
62
40
4
41
52
42
76
43
45
44
55
45
3
46
64
47
71
48
16
49
35
50
80
51
22
52
12
53
42
54
34
55
39
56
68
57
9
58
65
59
14
60
28
61
23
62
58
63
18
64
69
65
13
66
10
67
48
68
72
69
40
70
50
71
21
72
2
73
19
74
30
75
15
76
54
77
11
78
74
79
0 / 1,605 ops ( 0.0%) 0.0%
Sorting is
a spectacle.
Algorithms at work, in a daily vertical feed. Watch, play, challenge — and go deeper when you're ready.
Loading 0%
An unhandled error has occurred. Reload 🗙