How It Works
Sort Target
Algorithm
Speed
Normal ~12s · 98 ms/step
Drop-Merge sort(2017)
▶ Try this Source
O(n log n) ✗ Stable ✗ In-place ✓ Adaptive

Combined with: Quicksort (Median3) (part of the process), Quicksort (Median3) (fallback)

🔧 How it works

Scans the input once to identify the longest non-decreasing subsequence already in place, collects all out-of-order "dropped" elements into a separate buffer, sorts that buffer, then merges it back with the in-order portion.

🎯 Key property

On nearly-sorted data with only k out-of-place elements the sort cost shrinks to O((k+1) log(k+1) + n), the sparser the drops, the faster the algorithm, approaching O(n) as k approaches 0.

👁 Watch for
  • Compare (drop detection) each element is tested against the last accepted value; elements that break the non-decreasing order are extracted and collected into a separate buffer
  • IndexRead extracted "drop" elements are lifted out of the array into the buffer while the forward scan continues past them
  • Compare (merge) after the buffer is sorted, a standard merge compares the buffer's front element against the surviving in-order portion to determine write order
  • IndexWrite the winning value from each merge step is written back, interleaving the sorted drops with the in-order run
🕰 History 🌳 Lineage ⚡ Optimization
UsesEarly-Out HeuristicDrop-Based Techniques
Initial State
This is the array before sorting. Follow Drop-Merge sort step by step.
Main Array
5
0
3
1
8
2
1
3
9
4
2
5
7
6
4
7
0 / 122 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 🗙