Merge Sort & Quicksort

The last lesson left the three quadratic sorts stuck against a wall: every one of them is Θ(n²), hopeless on a million items. Divide and conquer is how you break through. Instead of nudging one element at a time, it splits the array, sorts each half, and combines the results — and the splitting is exactly what buys the speed. Two algorithms dominate the exam, and they make opposite trade-offs: mergesort is rock-solid and predictable; quicksort is usually faster but can blow up. Knowing exactly when each wins is what GATE tests — and it is the same judgement you make in real work, where df.sort_values() and the merge-join behind every database JOIN rest on exactly these two patterns.

Divide and conquer, in one picture

The pattern is always the same three steps — divide the input into smaller pieces, conquer each piece recursively, then combine the answers.

Mergesort — split, sort, merge

Mergesort splits the array in half, recursively sorts each half, and then merges the two sorted halves into one. The recursion tree has depth log n, and each level does Θ(n) work to merge, so the total is always Θ(n log n) — best, average, and worst case alike. There are no bad inputs, ever.

The cost is space: merging needs a temporary buffer, so mergesort uses O(n) extra memory. The benefit is that it is stable — equal keys keep their original relative order, because the merge step always takes from the left half first on a tie.

Quicksort — pick a pivot, partition, recurse

Quicksort picks one element as the pivot, then partitions the array so that everything smaller than the pivot goes left and everything larger goes right. The pivot is now in its final sorted position; recurse on the two sides. No merge step is needed — the work happens before the recursion, and it is done in place (O(1) extra space beyond the recursion stack).

When the pivot splits the array roughly in half each time, the recursion depth is log n and quicksort runs in Θ(n log n) on average. But if the pivot is always the smallest or largest element, one side is empty and the other has n − 1 elements — the recursion becomes n levels deep, each doing Θ(n) comparisons, giving the worst case Θ(n²). Quicksort is also not stable: partitioning swaps far-apart elements and scrambles the order of equal keys.

How GATE asks this

A favourite NAT: give a small array and a fixed pivot rule, then ask for the number of swaps or comparisons (GATE DA 2024, Q.30 did exactly this — covered below). The 2026 paper leaned on the merge step, asking what a partial merge computes — the door to counting inversions. An inversion is a pair (i, j) with i < j but a[i] > a[j]; it measures how far from sorted an array is. The merge step counts them for free: when you take an element from the right half, every element still remaining in the left half is larger than it, so each forms an inversion with it. A fully reverse-sorted array of n items has the maximum n(n−1)/2 inversions — for n = 5 that is 10.

Worked example — a real 2024 question

GATE DA 2024, Q.30. Consider sorting [60, 70, 80, 90, 100] in ascending order using an in-place quicksort that uses the last element as the pivot. The minimum number of swaps performed is ______.

The array is already sorted ascending. Walk the standard in-place partition (the Lomuto scheme, last element as pivot):

[60, 70, 80, 90, 100]   pivot = 100 (last)
  scan 60,70,80,90 — every one is < 100, so each is already on the
  "smaller" side and stays put: 0 swaps. The pivot 100 is already in its
  final slot, so no swap is needed to place it either.
  -> partition does 0 swaps; pivot fixed at the end.

recurse on [60, 70, 80, 90]   pivot = 90 — same story, 0 swaps.
recurse on [60, 70, 80]       pivot = 80 — 0 swaps.
recurse on [60, 70]           pivot = 70 — 0 swaps.

Every element is already on the correct side of every pivot, and every pivot is already in its final position, so the minimum number of swaps is 0 — the official answer to this NAT.

But do not mistake “0 swaps” for “fast.” This sorted input is quicksort’s worst case for comparisons: each partition shrinks the array by only one element, so the comparison count is 4 + 3 + 2 + 1 = 10 = n(n−1)/2, the Θ(n²) pattern. Zero data movement, maximum comparisons — picking the largest element as pivot every time produces maximally unbalanced recursion.

Here is that partition with a swap counter, run on both the sorted input and its reverse:

def quicksort_swaps(a):
    a = a[:]
    swaps = 0
    def part(lo, hi):
        nonlocal swaps
        pivot = a[hi]            # last element as pivot
        i = lo - 1
        for j in range(lo, hi):
            if a[j] <= pivot:
                i += 1
                if i != j:       # only a real swap counts
                    a[i], a[j] = a[j], a[i]; swaps += 1
        if i + 1 != hi:          # pivot already in place => no swap
            a[i+1], a[hi] = a[hi], a[i+1]; swaps += 1
        return i + 1
    def qs(lo, hi):
        if lo < hi:
            p = part(lo, hi); qs(lo, p-1); qs(p+1, hi)
    qs(0, len(a)-1)
    return swaps, a

print(quicksort_swaps([60, 70, 80, 90, 100]))
print(quicksort_swaps([100, 90, 80, 70, 60]))

prints:

(0, [60, 70, 80, 90, 100])
(2, [60, 70, 80, 90, 100])

Even the reverse-sorted input moves only two elements — yet both inputs are the Θ(n²) comparison worst case. Swap count and comparison count are different things: quicksort’s pain on extreme-pivot input is all in the comparisons, not the data movement.

A question to carry forward

Look at what made both these sorts work: recursion. Mergesort recurses down to single elements; quicksort recurses on each side of the pivot. And every recursive call quietly piles onto the computer’s call stack — a last-in, first-out ledger that grows as you descend and pops as you return. That stack is not mere plumbing; it is a fundamental data structure in its own right, with a first-come-first-served sibling. Here is the thread onward: how do a stack (LIFO) and a queue (FIFO) actually work, what operations do they support in O(1), and where does each one’s discipline turn up — from undo buttons to print jobs to the recursion you just traced?

In one breath

• Divide and conquer: split → solve halves recursively → combine. Both sorts split in two.
• Mergesort: always Θ(n log n) (no bad inputs), stable, but needs O(n) extra space for the merge buffer.
• Quicksort: average Θ(n log n), in-place, but Θ(n²) worst case (extreme pivot, e.g. sorted input with first/last pivot) and not stable.
• The 2024 trap: a sorted array gives quicksort 0 swaps yet is its Θ(n²) comparison worst case — swaps ≠ comparisons.
• Inversions (pairs out of order) measure unsortedness; the merge step counts them free; max is n(n−1)/2 (10 for n=5).

Practice