# Merge Sort and Quick Sort — Divide and Conquer Sorting

Source: https://skills101.in/learn/dsa/dsa-merge-sort-quick-sort — Skills101 free tutorial (Data Structures & Algorithms). Updated 2026-11-17.

Bubble, selection and insertion sort are O(n²). To sort 10⁵ or 10⁶ items you need **O(n log n)**. The two classic ways to get there both use **divide and conquer**: break the problem into smaller copies of itself, solve those, and combine the answers.

- **Merge sort:** split the array in half, sort each half, then **merge** the two sorted halves.
- **Quick sort:** pick a **pivot**, move smaller items to its left and larger to its right, then sort each side.

## 1. Merge sort

![Merge sort on 6 3 8 1 5 2 7 4: the array is split into halves three times down to pairs, then merged back: 3 6, 1 8, 2 5, 4 7, then 1 3 6 8 and 2 4 5 7, and finally 1 2 3 4 5 6 7 8](https://skills101.in/learn-img/dsa/merge-sort.svg)

The real work happens in the **merge** step. Two sorted lists are combined by repeatedly taking the smaller front item:

```python
def merge(left, right):
    out, i, k = [], 0, 0
    while i < len(left) and k < len(right):
        if left[i] <= right[k]:          # <= keeps equal items in order (stable)
            out.append(left[i]); i += 1
        else:
            out.append(right[k]); k += 1
    return out + left[i:] + right[k:]    # one side may still have items

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    return merge(merge_sort(a[:mid]), merge_sort(a[mid:]))

print(merge([1, 3, 6, 8], [2, 4, 5, 7]))
print(merge_sort([6, 3, 8, 1, 5, 2, 7, 4]))
```

```text
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
```

**Why O(n log n)?** Halving 8 items reaches size 1 after log₂ 8 = 3 levels. On each level, the merges together touch all n items once. So the total is n × log n — and that holds in the **best, average and worst** case.

**Cost:** merge sort needs **O(n) extra memory** for the merged lists. It is **stable**, which is why Java uses a merge-sort variant (Timsort) for sorting objects.

## 2. Quick sort

Quick sort does its work **before** recursing. The **partition** step picks a pivot and rearranges the array so that every smaller item comes before it and every larger item after it. The pivot is then in its **final** position.

![Lomuto partition of 7 2 9 4 3 8 5 with pivot 5: after partitioning the array is 2 4 3 5 9 8 7, smaller items on the left, the pivot 5 at its final index 3, larger items on the right](https://skills101.in/learn-img/dsa/quick-partition.svg)

This is the **Lomuto partition** — the easiest version to write in an interview:

```python
def partition(a, lo, hi):
    pivot = a[hi]
    i = lo - 1                      # a[lo..i] holds items smaller than the pivot
    for k in range(lo, hi):
        if a[k] < pivot:
            i += 1
            a[i], a[k] = a[k], a[i]
    a[i + 1], a[hi] = a[hi], a[i + 1]
    return i + 1

def quick_sort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo < hi:
        p = partition(a, lo, hi)
        quick_sort(a, lo, p - 1)
        quick_sort(a, p + 1, hi)
    return a

b = [7, 2, 9, 4, 3, 8, 5]
print(partition(b, 0, len(b) - 1), b)
print(quick_sort([7, 2, 9, 4, 3, 8, 5]))
```

```text
3 [2, 4, 3, 5, 9, 8, 7]
[2, 3, 4, 5, 7, 8, 9]
```

### Quick sort's worst case

If the pivot is always the smallest or largest item — for example, the last element of an **already sorted** array — each partition removes only one item. That gives n levels of n work: **O(n²)**.

The fix is to choose the pivot **randomly** (swap a random item to the end first). Then the expected time is O(n log n) on every input. Quick sort sorts **in place** (only O(log n) stack space on average) and is very fast in practice, so Java's `Arrays.sort` for primitive arrays uses a quick sort variant (dual-pivot quick sort).

### Quick sort in Java (random pivot)

```java
import java.util.Arrays;
import java.util.Random;

public class Main {
    static Random rnd = new Random(42);

    static int partition(int[] a, int lo, int hi) {
        int r = lo + rnd.nextInt(hi - lo + 1);       // random pivot → expected O(n log n)
        int t = a[r]; a[r] = a[hi]; a[hi] = t;
        int pivot = a[hi], i = lo - 1;
        for (int k = lo; k < hi; k++) {
            if (a[k] < pivot) {
                i++;
                t = a[i]; a[i] = a[k]; a[k] = t;
            }
        }
        t = a[i + 1]; a[i + 1] = a[hi]; a[hi] = t;
        return i + 1;
    }

    static void quickSort(int[] a, int lo, int hi) {
        if (lo >= hi) return;
        int p = partition(a, lo, hi);
        quickSort(a, lo, p - 1);
        quickSort(a, p + 1, hi);
    }

    public static void main(String[] args) {
        int[] a = {10, 80, 30, 90, 40, 50, 70};
        quickSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }
}
```

```text
[10, 30, 40, 50, 70, 80, 90]
```

## 3. Merge sort vs quick sort

| | Merge sort | Quick sort |
|---|---|---|
| Time (worst) | O(n log n) | O(n²), rare with a random pivot |
| Time (average) | O(n log n) | O(n log n), usually faster in practice |
| Extra memory | O(n) | O(log n) for recursion |
| Stable? | yes | no |
| Good for | linked lists, stable sorting, huge files on disk | arrays in memory |

## 4. Patterns built on these ideas

- **Merge step:** "merge two sorted arrays", "merge k sorted lists" and **counting inversions** (count pairs while merging).
- **Partition step:** **quickselect** finds the k-th smallest item in O(n) on average — partition, then recurse into only the side that contains index k.
- **Sort first, then solve:** many problems (meeting rooms, two-sum on a sorted array, intervals) become easy after an O(n log n) sort.

## Common mistakes

- Writing `<` instead of `<=` in merge — the result is still sorted, but the sort is no longer stable.
- Forgetting to copy the leftovers (`left[i:]`, `right[k:]`) after the merge loop.
- Quick sort recursing on `(lo, p)` instead of `(lo, p − 1)` — the pivot is already in place, and including it can recurse forever.
- Using the last element as pivot on sorted input and getting O(n²) — pick a random pivot.

## Quick recap

- Both are divide and conquer and run in O(n log n) on average.
- Merge sort: split, sort halves, merge; always O(n log n); stable; O(n) extra memory.
- Quick sort: partition around a pivot, then sort both sides; in place; worst case O(n²) — use a random pivot.
- The merge step and the partition step are themselves interview patterns.


Practice quiz and free certificate: https://skills101.in/learn/dsa/dsa-merge-sort-quick-sort