1. One-Liner
Merge sort splits the array into two halves, sorts each half recursively, and merges two sorted sequences into one sorted array.
2. The Problem It Solves
You need a predictable O(n log n) comparison sort with stable merging behavior—common in external sorting, linked lists, and parallel pipelines where divide-and-conquer maps cleanly to tasks.
3. The Core Idea
Divide the problem into two equal subproblems, conquer them independently, then combine with a linear merge that walks two pointers—like zipping two sorted decks of cards.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|
| 1. Base case | If length ≤ 1, the segment is already sorted. |
|---|
| 2. Split | Find mid index; recurse on [lo, mid) and [mid, hi). |
|---|
| 3. Merge | Two-pointer merge from temporary left/right buffers into the original range. |
|---|
| 4. Stability | When keys tie, take from the left run first to preserve order. |
|---|
5. Dry Run Example
Array: [38, 27, 43, 3]
| Phase | Result |
|---|
| Split & sort leaves | [27,38] and [3,43] |
|---|
| Merge pairs | [27,38] and [3,43] |
|---|
| Final merge | [3,27,38,43] |
|---|
6. Key Properties
| Property | Value |
|---|
| Time | O(n log n) all cases (typical merge) |
|---|
| Space | O(n) auxiliary for merge buffers |
|---|
| Stable | Yes (with ≤ merge rule) |
|---|
| Adaptive | Not inherently adaptive |
|---|
7. Where It Is Used
| Domain | Use |
|---|
| Databases / files | External merge sort on large runs |
|---|
| Functional libs | Immutable list sorting via merge |
|---|
| Parallel systems | Fork sub-sorts, merge results |
|---|
8. Interview Tips
State recurrence T(n)=2T(n/2)+O(n) → O(n log n), mention stable merge, contrast space vs quicksort’s in-place average case.
9. Comparison with Other Algorithms
| Algorithm | Time (worst) | Space | Stable |
|---|
| Merge sort | O(n log n) | O(n) | Yes |
|---|
| Quick sort | O(n²) | O(log n) stack | No |
|---|
| Heap sort | O(n log n) | O(1) | No |
|---|
10. Complexity
| Metric | Value |
|---|
| Time (Best/Avg/Worst) | O(n log n) |
|---|
| Space | O(n) auxiliary |
|---|
| 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 = 0
out = []
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
return out + a[i:] + b[j:]