Merge Sort & Quicksort

The basic sorts moved one element at a time and paid Θ(n²) for it. Divide and conquer does better by splitting the array, sorting each half, and combining the results. 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 are built 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.

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 — the picking of the largest element as pivot every time produces maximally unbalanced recursion.

Quick check