Sort Target
Algorithm
Speed
Normal ~12s · 32 ms ×3
Natural merge sort(1973)
▶ Try this Source
O(n log n) ✓ Stable ✗ In-place
🔧 How it works

Scans the entire array to detect naturally occurring runs, both ascending (non-decreasing) and strictly descending sequences. Descending runs are reversed in-place to become ascending. Adjacent pairs of runs are then merged, and the process repeats until a single sorted run remains.

🎯 Key property

Adaptive, already-sorted or fully-reversed input is handled in O(n) because it forms a single run, requiring only one detection scan and no merges. Unlike standard Merge sort, it is iterative with no recursion.

👁 Watch for
  • Compare adjacent pairs are tested during run detection to find run boundaries and determine ascending vs. descending direction
  • Swap strictly descending runs are reversed in-place by swapping symmetric pairs around the midpoint
  • RangeCopy during merge, the left run is copied into an auxiliary buffer; sorted values are then written back as the two runs are combined
🕰 History 🌳 Lineage ⚡ Optimization
UsesRun Detection
Initial State
This is the array before sorting. Follow Natural merge sort step by step.
Main Array
25
0
26
1
27
2
28
3
29
4
30
5
31
6
32
7
24
8
23
9
22
10
21
11
20
12
19
13
18
14
17
15
33
16
34
17
35
18
36
19
37
20
38
21
39
22
40
23
16
24
15
25
14
26
13
27
12
28
11
29
10
30
9
31
41
32
42
33
43
34
44
35
45
36
46
37
47
38
48
39
8
40
7
41
6
42
5
43
4
44
3
45
2
46
1
47
57
48
58
49
59
50
60
51
61
52
62
53
63
54
64
55
56
56
55
57
54
58
53
59
52
60
51
61
50
62
49
63
RunsDetect 0 runs on stack
Waiting for run detection…
0 / 1,112 ops ( 0.0%) 0.0%
• © 2026 guitarrapc. All rights reserved.
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 🗙