DSA Sorting
Merge Sort
Dual conflict: the analytics export must stay stable for equal timestamps, and the SLA forbids a surprise Theta(n^2) spike when pivots go bad.
Merge sort splits, sorts halves, and combines with a linear two-pointer merge. You buy predictable Theta(n log n) time and , paying on arrays. It meets the comparison-sort up to constants.
Algorithm journey
Split
Halve ranges until length 0 or 1.
Sort halves
Each half becomes a sorted run.
Stable merge
Two pointers emit the next smallest key; ties prefer left.
log n levels
Each level moves Theta(n) items; depth is Theta(log n).
What actually happens
Naive idea: recursively sort with an unstable in-place method and hope equals stay put. They will not, and adversarial pivots can square the runtime.
Better idea: make ordering happen in the merge, where the proof is local and the level cost is linear.
It still costs a buffer (or pointer splicing), and constant factors can lose to tuned quicksort/introsort when stability is irrelevant and memory is tight.
Invariant
After merging two sorted runs, the output prefix holds exactly the smallest consumed items in sorted order, preserving equal-key order when ties take from the left run.
How to choose merge sort
1. Need stability or a hard Theta(n log n) ceiling? Merge sort (or TimSort) is the safe comparison-sort pick.
2. External / linked data? Run-based merging and list mergesort are natural fits.
3. Tiny nearly sorted arrays? Insertion often wins on constants; hybrids steal that idea.
Quantitative check
n = 10^6: about log2 n ≈ 20 merge levels, each Theta(n) moves, so on the order of 2 x 10^7 element placements plus comparisons. Worst and average share the same Theta(n log n) class.
Average / worst
Θ(n log n)
Array auxiliary
Θ(n)
Stable
Yes, with left-first ties
Adaptive by default
No (natural variants are)
The merge is where ordering happens
The recursive split only creates smaller problems. Step through the linear merge and watch equal tagged records preserve their input order.
Stable merge lab
Merge two sorted runs in one pass
L/R tags track original halves so equal-key stability remains visible.
comparisons
0
writes
0
Left sorted half
Right sorted half
Output buffer
0 / 6 placed
Both halves are already sorted.
Invariant: Only their front unconsumed values can be the next global minimum.
globally smallest consumed items
smallest remaining in each run
left first ⇒ stable ordering
Original interactive merge-sort visualizer (retained)
Run, pause, or step through the original whole-array animation after studying the focused two-run merge above.
Split tree, merge levels
Divide
Halve ranges until each has zero or one element, which is sorted by definition.
Merge invariant
The output prefix holds exactly the smallest consumed items in sorted order.
Finish
After log₂n merge levels, one sorted run spans the entire input.
One reusable buffer, half-open ranges
This version allocates one auxiliary array and reuses it at every recursion level. Ranges are[lo, hi), so their length is hi − lo and the base case is unambiguous.
Python
1def merge_sort(a):
2 aux = [None] * len(a)
3
4 def sort(lo, hi): # sort a[lo:hi]
5 if hi - lo <= 1:
6 return
7
8 mid = lo + (hi - lo) // 2
9 sort(lo, mid)
10 sort(mid, hi)
11
12 # Optional adaptive shortcut: the runs already join in order.
13 if a[mid - 1] <= a[mid]:
14 return
15
16 for k in range(lo, hi):
17 aux[k] = a[k]
18
19 left, right = lo, mid
20 for out in range(lo, hi):
21 if left == mid:
22 a[out] = aux[right]
23 right += 1
24 elif right == hi:
25 a[out] = aux[left]
26 left += 1
27 elif aux[right] < aux[left]:
28 a[out] = aux[right]
29 right += 1
30 else:
31 a[out] = aux[left] # left wins ties => stable
32 left += 1
33
34 sort(0, len(a))Java
1final class MergeSort {
2 static void sort(int[] a) {
3 int[] auxiliary = new int[a.length];
4 sort(a, auxiliary, 0, a.length);
5 }
6
7 // Sort the half-open range a[lo, hi).
8 private static void sort(int[] a, int[] auxiliary, int lo, int hi) {
9 if (hi - lo <= 1) return;
10
11 int mid = lo + (hi - lo) / 2;
12 sort(a, auxiliary, lo, mid);
13 sort(a, auxiliary, mid, hi);
14
15 // The adjacent runs already join in order.
16 if (a[mid - 1] <= a[mid]) return;
17
18 System.arraycopy(a, lo, auxiliary, lo, hi - lo);
19 int left = lo;
20 int right = mid;
21
22 for (int out = lo; out < hi; out++) {
23 if (left == mid) {
24 a[out] = auxiliary[right++];
25 } else if (right == hi) {
26 a[out] = auxiliary[left++];
27 } else if (auxiliary[right] < auxiliary[left]) {
28 a[out] = auxiliary[right++];
29 } else {
30 // Left wins ties, preserving stability.
31 a[out] = auxiliary[left++];
32 }
33 }
34 }
35}Why the merge is correct
Initialization
The empty output prefix is sorted and contains the zero smallest input items.
Maintenance
Each run is sorted, so the smaller front is the smallest unconsumed item overall. Appending it preserves order.
Termination
Every step consumes one item. When a run empties, the other suffix is already sorted and can be copied directly.
Induct on range length: recursive calls correctly sort both shorter halves; the merge lemma above correctly combines any two sorted halves; therefore the full range is sorted.
The recurrence and the real costs
Time
T(n) = 2T(n/2) + Θ(n)
Each level merges Θ(n) total items, and balanced halving creates Θ(log n) levels. Input order does not change the standard algorithm’s asymptotic bound.
Space
Θ(n) buffer + Θ(log n) stack
The reusable array dominates auxiliary memory. Bottom-up merge sort removes the recursion stack but still needs the array buffer for a straightforward stable merge.
| Case | Comparisons / moves | Why |
|---|---|---|
| Best, standard | Θ(n log n) | All levels still merge without the ordered-run shortcut. |
| Best, adaptive check | O(n) comparisons | Already ordered adjacent runs skip copying and merging at every level. |
| Average / worst | Θ(n log n) | Every element participates once per merge level. |
Stability is one comparison operator
Suppose equal records 2L and 2R came from the left and right halves. Because every left-half item originally preceded every right-half item, equality must select2L first. Compare “right < left,” not “right ≤ left.”
Easy stability bug
Taking from the right on equality silently reverses equal records that straddle a split.
Stability enables multi-key sorting: stably sort by a secondary key, then stably sort by the primary key. Equal primary-key records retain the established secondary-key order.
Variants follow the storage model
| Variant | How runs appear | Best fit | Tradeoff |
|---|---|---|---|
| Top-down | Recursive halving | Clear proof and implementation | O(log n) call stack |
| Bottom-up | Merge runs of width 1, 2, 4, … | No recursion; predictable passes | Careful final partial-run bounds |
| Natural merge sort | Discover existing ordered runs | Partially sorted real data | Run detection and merge policy are more involved |
| Linked-list merge sort | Split links, splice nodes | No random access required; O(1) merge storage | Pointer-heavy implementation |
| External merge sort | Sort memory-sized runs, then k-way merge | Data larger than RAM | I/O and buffering dominate CPU comparisons |
Patterns built on merging
Count inversions
When a right item beats the left front, it forms inversions with every remaining left item. Count them during merge in Θ(n log n).
External sorting
Create sorted disk runs that fit in memory, then merge buffered heads with a heap. Sequential I/O is the main advantage.
Merge linked lists
Relink the smaller front node instead of copying array elements; this is why merge sort fits linked lists naturally.
Parallel sorting
The two recursive halves are independent, and large merges can also be partitioned for parallel execution.
Sort by multiple fields
Stability preserves an earlier ordering among records whose current keys tie.
Count/rank problems
Merge-time cross-half reasoning solves reverse pairs, range sums, and related divide-and-conquer counting tasks.
Merge Sort vs Quick Sort
| Concern | Merge Sort | Quick Sort |
|---|---|---|
| Worst-case time | Θ(n log n) | Θ(n²), unless guarded by a fallback |
| Array auxiliary memory | Θ(n) | O(log n) expected stack |
| Stability | Natural with left-first ties | Usually unstable |
| Storage fit | Linked lists, external files, stable records | Contiguous in-memory arrays |
Implementation checklist
- • Use one boundary convention consistently; half-open ranges simplify lengths.
- • Select from the left on equality when stability is required.
- • Copy every remainder after one run is exhausted.
- • Allocate one reusable buffer instead of new slices at every node.
- • Test empty, singleton, odd-length, duplicate, and already sorted arrays.
- • Ensure midpoint and run endpoints cannot exceed the active range.
Exercises
- Show a merge of two runs where taking the right equal key first breaks stability.
- Bottom-up vs top-down: which uses recursion stack, and how does that change auxiliary space beyond the buffer?
- Why does a comparison-sort lower bound not forbid counting/radix sorts from beating n log n on integers?
Primary sources
- Cormen et al., Introduction to Algorithms (CLRS): merge sort and the decision-tree lower bound.
- Knuth, The Art of Computer Programming, Vol. 3: merging and multiway merge.
- Python TimSort description (CPython): natural runs as a merge-sort descendant.
Decision rule
Choose Merge Sort when stability, a deterministic Θ(n log n) bound, sequential external I/O, or linked-list structure matters more than the Θ(n) array buffer. The merge primitive is also worth learning independently: many counting and streaming algorithms reuse it.