# 8.3 Merge Sort

> Split the array in half, sort each half recursively, then merge the two sorted halves. Always O(n log n), stable, but needs O(n) extra space.

Chapter: Advanced Sorting & Searching · ~50 min · medium
URL: https://dsa.fetehadin.com/learn/merge-sort

## Mental model

Two people each hold a **sorted pile** of cards. To combine them, look at the top card of each pile, take the smaller one, and repeat. That **merge** is easy and takes one look per card.

Merge sort uses that trick recursively:

1. **Divide**: split the array into two halves.
2. **Conquer**: sort each half (recursively, until a piece has 1 item, which is already sorted).
3. **Combine**: merge the two sorted halves.

### The merge

```cpp
while (i <= mid && j <= hi)
    tmp.push_back(a[i] <= a[j] ? a[i++] : a[j++]);
// then copy whatever is left of either half
```

Using `<=` takes the **left** item when two are equal, so equal items keep their order: merge sort is **stable**.

### Why always n log n

Halving n repeatedly reaches 1 after **log₂ n** levels. Each level merges n items in total. So the cost is **n log n**, for sorted, reversed or random data alike. The price is the **O(n) temporary array**.

### Merge vs quick

| | Merge sort | Quick sort |
| --- | --- | --- |
| Worst case | O(n log n) | O(n²) |
| Extra space | O(n) | O(log n) |
| Stable | yes | no |

## C++ code: merge-sort.cpp

```cpp
#include <iostream>
#include <vector>
using namespace std;

void merge(int a[], int lo, int mid, int hi) {
    vector<int> tmp;                          // O(n) extra space
    int i = lo, j = mid + 1;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) tmp.push_back(a[i++]);   // <= keeps it stable
        else tmp.push_back(a[j++]);
    }
    while (i <= mid) tmp.push_back(a[i++]);
    while (j <= hi) tmp.push_back(a[j++]);
    for (int k = 0; k < (int)tmp.size(); k++) a[lo + k] = tmp[k];
}

void mergeSort(int a[], int lo, int hi) {
    if (lo >= hi) return;                     // 0 or 1 item: already sorted
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid);
    mergeSort(a, mid + 1, hi);
    merge(a, lo, mid, hi);
    cout << "merged [" << lo << ".." << hi << "]: ";
    for (int k = lo; k <= hi; k++) cout << a[k] << " ";
    cout << "\n";
}

int main() {
    int a[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(a) / sizeof(a[0]);
    mergeSort(a, 0, n - 1);
    cout << "sorted: ";
    for (int x : a) cout << x << " ";
    cout << "\n";
}
```

Expected output:

```text
merged [0..1]: 27 38 
merged [2..3]: 3 43 
merged [0..3]: 3 27 38 43 
merged [4..5]: 9 82 
merged [4..6]: 9 10 82 
merged [0..6]: 3 9 10 27 38 43 82 
sorted: 3 9 10 27 38 43 82
```

## Complexity

| Case | Cost |
| --- | --- |
| Best case | O(n log n) |
| Average case | O(n log n) |
| Worst case | O(n log n) |

Space: O(n) for the temporary array
Stable: yes
In-place: no

log₂ n levels of splitting, and each level does O(n) merging work, so **n log n** whatever the input.

## Videos

- [Merge Sort Algorithm](https://youtu.be/mB5HXBb_HY8) (Abdul Bari): Abdul Bari draws the full recursion tree and derives n log n.
- [Merge sort in 3 minutes](https://youtu.be/4VqmGXwpLqc) (Michael Sambol): The 3-minute visual version.

## Exam lens

Likely questions:

- Show the split and merge tree of merge sort on `38, 27, 43, 3, 9, 82, 10`.
- Write the merge function. Why is merge sort O(n log n) in every case?
- Compare merge sort and quick sort (time, space, stability).

Common mistakes:

- Forgetting to copy the leftover items after one half runs out.
- Using `<` instead of `<=` in merge, which breaks stability.
- Base case `lo > hi` only. A single item (`lo == hi`) must also stop the recursion.
- Calling merge sort in-place.

## Quick check

1. Merge `2 5 9` and `1 5 7`. Result and number of comparisons?
   A. `1 2 5 5 7 9`, 5 comparisons
   B. `1 2 5 5 7 9`, 6 comparisons
   C. `2 5 9 1 5 7`, 0
   D. `1 2 5 7 9`, 5
   Answer: A. Comparisons: 2/1, 2/5, 5/5, 9/5, 9/7. Then 9 is copied without comparing.

2. Worst-case time of merge sort?
   A. O(n)
   B. O(n log n)
   C. O(n²)
   D. O(log n)
   Answer: B. The splits are always even, whatever the data.

3. Main disadvantage of merge sort compared with quick sort?
   A. Worse worst case
   B. Needs O(n) extra memory
   C. Not stable
   D. Only works on linked lists
   Answer: B. The merge step writes into a temporary array.

## Practice

**Trace by hand.** Trace merge sort on `38, 27, 43, 3, 9, 82, 10`. Write every merge in the order it happens.

Solution:

- merge [0..1]: `27 38`
- merge [2..3]: `3 43`
- merge [0..3]: `3 27 38 43`
- merge [4..5]: `9 82`
- merge [4..6]: `9 10 82`
- merge [0..6]: `3 9 10 27 38 43 82`


**Implement it.** Count inversions (pairs i < j with a[i] > a[j]) by modifying merge sort.

Hint: When you take from the right half, every item left in the left half is bigger, so add `mid − i + 1`.

**Problems:**

- [Merge Sorted Array](https://leetcode.com/problems/merge-sorted-array/) (easy). Hint: Merge from the back so you don't overwrite nums1.
- [Sort List](https://leetcode.com/problems/sort-list/) (medium). Hint: Merge sort on a linked list. Find the middle with fast/slow pointers, split, sort, merge.

## Mastery checklist

- [ ] I can draw the split/merge tree by hand.
- [ ] I can write merge() and mergeSort() from memory.
- [ ] I can explain why it is always O(n log n).
- [ ] I know it is stable but needs O(n) extra space.