Back to Library
Natural Merge Sort
Divide and Conquer
Recursively breaks the problem into smaller sub-problems, solves them, and combines the results.
Hybrid
Combines two or more algorithms to leverage their specific strengths for different data sizes.
Adaptive
Performance improves significantly on data that is already partially sorted.
Out-of-Place
Requires auxiliary memory proportional to the input size (O(n)).
Stable
Preserves the relative order of elements with equal values.
Natural merge sort scans for existing ascending or strictly descending runs. It reverses descending runs and merges adjacent runs until one remains.
Visualize Fullscreen
Demo
20 elements • 4x Speed
No Data
Did you know?
- An already sorted array forms one natural run, so this implementation finishes without performing a merge.
- Only strictly descending runs are reversed; equal neighbors stay in their original order for stability.
- Tim Peters’s Timsort also looks for natural runs, then adds ideas such as minimum run lengths and galloping merges. This site’s natural merge sort keeps the run-detection idea without those extra policies.
How it Works
-
Scan the array for maximal ordered runs.
-
Reverse strictly descending runs; equal keys stay in input order.
-
Merge neighboring runs stably, then repeat.
Complexity Analysis
Advantages
- Linear behavior on already sorted input.
- Stable handling of equal values.
Disadvantages
- Requires an auxiliary merge buffer.
Implementation
JavaScript natural-merge-sort.js
function naturalMergeSort(a) {
const merge = (lo, mid, hi) => {
const x = a.slice(lo, mid), y = a.slice(mid, hi);
let i = 0, j = 0, k = lo;
while (i < x.length || j < y.length)
a[k++] = j === y.length || (i < x.length && x[i] <= y[j]) ? x[i++] : y[j++];
};
while (a.length > 1) {
const runs = [];
for (let lo = 0; lo < a.length;) {
let hi = lo + 1;
const down = hi < a.length && a[lo] > a[hi];
while (hi < a.length && (down ? a[hi - 1] > a[hi] : a[hi - 1] <= a[hi])) hi++;
if (down) a.splice(lo, hi - lo, ...a.slice(lo, hi).reverse());
runs.push([lo, hi]); lo = hi;
}
if (runs.length === 1) break;
for (let i = 0; i + 1 < runs.length; i += 2) merge(runs[i][0], runs[i][1], runs[i + 1][1]);
}
return a;
}