1. One-Liner
Merge Sort splits the array in half, sorts each half recursively, and merges the two sorted halves into one sorted output.
2. The Problem It Solves
You need guaranteed O(n log n) time for arbitrary inputs and stability (equal keys keep their relative order) — common in external sorting and as a building block of Tim Sort.
3. The Core Idea
Two piles of playing cards are already sorted face-up. Repeatedly take the smaller top card from either pile — the merged pile is sorted.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. | Base case: length ≤ 1 → already sorted |
| 2. | Split at midpoint mid |
| 3. | Recursively sort left [0, mid) and right [mid, n) |
| 4. | Merge: two pointers; always take the smaller head (left on ties for stability) |
| 5. | Append leftover elements from the longer tail |
5. Dry Run Example
Merge [1, 4] and [2, 3]: output 1, 2, 3, 4 — each step picks the minimum of the two fronts.
6. Key Properties
| Property | Value |
|---|---|
| Stable | Yes if left chunk is preferred when equal |
| Extra space | O(n) for typical array merge |
| Parallel | Left/right sorts are independent |
7. Where It Is Used
| Company / System | How They Use It |
|---|---|
| Java / Python TimSort | Merge runs of ordered data |
| External sort | Large files on disk in chunks |
8. Interview Tips
Be fluent in the merge routine; explain why total work is O(n log n) via recursion tree; compare to Quick Sort (in-place vs stable).
9. Comparison with Other Algorithms
| Algorithm | Worst time | Extra space | Stable |
|---|---|---|---|
| Merge | O(n log n) | O(n) | Yes |
| Quick | O(n²) | O(log n) stack | No |
| Heap | O(n log n) | O(1) | No |
10. Complexity
| Metric | Value |
|---|---|
| Time (Best) | O(n log n) |
| Time (Average) | O(n log n) |
| Time (Worst) | O(n log n) |
| Space | O(n) auxiliary (typical array merge) |
| Stable? | Yes |
Implementation Example (PYTHON)
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(a, b):
i, j, out = 0, 0, []
while i < len(a) and j < len(b):
if a[i] <= b[j]:
out.append(a[i]); i += 1
else:
out.append(b[j]); j += 1
out.extend(a[i:]); out.extend(b[j:])
return out