Merge Sort & Quick Sort — Algorithms Course

What you'll learn

Two algorithms broke the O(n²) barrier with the same idea — divide and conquer — yet feel completely different. Merge sort is stable and predictable; quick sort is in-place and, in practice, the fastest general sort there is.

By the end you'll be able to:

Explain the divide-and-conquer structure of both sorts
Perform the merge and partition steps
Explain quick sort's worst case and how to avoid it
Choose between them for a given situation

Merge sort

Split the array in half, sort each half recursively, then merge the two sorted halves with a two-pointer walk. There are log n levels of splitting and each merge level touches all n elements — a guaranteed O(n log n). Watch the runs double each pass:

Merge sort (bottom-up)

Merge sort

1/5Merge sort: treat each element as a sorted run of size 1, then merge adjacent runs, doubling the run size each pass.

Each pass merges adjacent sorted runs, doubling their size until one run remains.

Merge in code

Language

merge_sort.py

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])          # divide
    right = merge_sort(a[mid:])
    return merge(left, right)           # combine

def merge(l, r):
    out, i, j = [], 0, 0
    while i < len(l) and j < len(r):
        if l[i] <= r[j]:                # <= keeps it stable
            out.append(l[i]); i += 1
        else:
            out.append(r[j]); j += 1
    return out + l[i:] + r[j:]

Note

Merge sort's O(n log n) holds in every case, and it's stable — but it needs O(n) extra space for the merge. It also shines on linked lists, where splitting and merging need no random access.

Quick sort

Pick a pivot, partition the array so smaller values go left and larger go right, then recurse on each side. The pivot lands in its final position every time. On average it's O(n log n) and, because it sorts in place, usually outruns merge sort:

Quick sort

1/33Quick sort: pick a pivot, partition smaller values left and larger values right, then recurse on each side.

Partition around a pivot (last element), placing it in its final spot, then recurse on each side.

Quick in code

Language

quick_sort.py

def quick_sort(a, lo=0, hi=None):
    if hi is None: hi = len(a) - 1
    if lo >= hi: return a
    p = partition(a, lo, hi)
    quick_sort(a, lo, p - 1)            # left of pivot
    quick_sort(a, p + 1, hi)            # right of pivot
    return a

def partition(a, lo, hi):
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]; i += 1
    a[i], a[hi] = a[hi], a[i]
    return i

Watch out

If the pivot is always the smallest or largest element (e.g. an already-sorted array with a last-element pivot), partitions are maximally unbalanced and quick sort degrades to O(n²). Fixes: pick a random pivot or the median-of-three.

Merge vs quick

	Merge sort	Quick sort
`Average time`	O(n log n)	O(n log n)
`Worst time`	O(n log n)	O(n²) (bad pivots)
`Space`	O(n)	O(log n) stack, in-place
`Stable?`	Yes	No (typical)
`Best for`	Linked lists, external, stability	Arrays in memory, raw speed

Recap & quick check

Key takeaways

Both use divide & conquer to reach O(n log n) average time.
Merge sort is stable and O(n log n) always, but needs O(n) extra space.
Quick sort sorts in place and is usually fastest, but risks O(n²) with bad pivots.
Random or median-of-three pivots make quick sort's worst case vanishingly unlikely.
Merge sort suits linked lists and external data; quick sort suits in-memory arrays.

Quick check

1. What is merge sort's worst-case time complexity?

2. When does quick sort degrade to O(n²)?

3. Which sort is stable and uses O(n) extra space?

4. What does quick sort's partition step guarantee?

There's one more O(n log n) sort — using a heap — plus sorts that beat it entirely. Next up: Module 9 — Heap Sort & Linear-Time Sorts.