Quick Sort

Quick sort is a divide-and-conquer sorting algorithm that picks a pivot value, partitions the array so everything smaller sits to the pivot's left and everything greater or equal to its right, and recurses on the two sides. It averages O(n log n) time, sorts in place, and degrades to O(n²) on adversarial pivots.

The pivot is a customs officer: every value in the range files past it exactly once and gets stamped smaller or not smaller. When the line ends, the officer takes the one seat that separates the two groups — and that seat is final. The pivot never moves again. Quick sort is just this checkpoint, run recursively on each side of the desk.

How Quick Sort Works

This lesson animates the Lomuto partition: the pivot is always arr[hi], the last value of the current range. Two pointers do the work. j scans every element from lo to hi − 1; i marks the boundary of the smaller-than-pivot zone — the next seat reserved for a small value.

When arr[j] < pivot, the value is stamped small: it swaps into slot i, and i advances. When arr[j] >= pivot, nothing moves; j walks on and the value stays in the right zone. After the scan, one last swap puts the pivot into slot i, exactly between the zones, and partition returns that index. The recursion then sorts arr[lo..p−1] and arr[p+1..hi] — the pivot itself is excluded, because it is already home.

Notice the asymmetry in the stamp: equal-to-pivot values go right. That, plus the long-distance swaps, is why quick sort is not stable.

Quick Sort Step by Step

The default input is [38, 12, 56, 7, 12, 41, 23], with two deliberate 12s — 12a at index 1, 12b at index 4 — so you can watch stability break.

Partition 1, range [0..6], pivot 23. Scan j = 0: 38 ≥ 23, stays right. j = 1: 12a < 23, swaps into slot 0 (i advances to 1). j = 2: 56 stays. j = 3: 7 < 23, swaps into slot 1. j = 4: 12b < 23, swaps into slot 2. j = 5: 41 stays. Final swap moves the pivot into index 3: [12a, 7, 12b, 23, 56, 41, 38]. Index 3 is done forever.

Partition 2, the left side [0..2] = [12a, 7, 12b], pivot arr[2] = 12b. Scan: 12a ≥ 12b — equal values fail the strict <, so 12a is stamped right. 7 < 12b swaps into slot 0. Pivot swap lands 12b at index 1: [7, 12b, 12a, 23, ...]. There it is — 12b now precedes 12a, their original order reversed by two swaps that never compared them to each other.

The rest compresses: [0..0] and [2..2] are single-element base cases. The right side [4..6] = [56, 41, 38] partitions on pivot 38; neither 56 nor 41 is smaller, so 38 swaps straight to index 4, leaving [38, 41, 56]. Its sub-range [5..6] picks pivot 56, which is already in its final seat. Result: [7, 12b, 12a, 23, 38, 41, 56] — sorted by value, shuffled by identity.

In the animation, the zone bands under the row are the partition's state made visible: the left band is the certified < pivot zone, the middle is scanned >= pivot, the rest is unknown territory j has not reached. A pivot snapping into place and turning green means one more index is permanently settled.

Time and Space Complexity

The animated version is plain Lomuto with a last-element pivot and no randomization — chosen because the mechanics stay readable, not because it is production-grade. The worst case is any input that keeps handing the partition its own minimum or maximum: each level then peels off a single element, and an already-sorted array — the most innocent-looking input there is — produces exactly that. Production implementations dodge it with random or median-of-three pivots; the time complexity bound is the same, but the bad inputs stop being predictable.

Edge Cases

• Empty or one-element ranges — base cases; the recursion bottoms out here (including the empty ranges a boundary pivot leaves behind).
• Already sorted or reverse-sorted input — worst case for the last-element pivot: maximally unbalanced partitions, O(n²).
• Duplicates — handled correctly by value, but quick sort is not stable; the default input's two 12s come out reordered.
• Values equal to the pivot — stamped >= pivot, so they all pile into the right zone; an all-equal array is another quadratic input for plain Lomuto.

Common Mistakes

• Recursing on [lo..p] or [p..hi]. Including the pivot's index re-sorts a settled element forever — the classic infinite recursion. Exclude p on both sides.
• Forgetting the final pivot swap. Without arr[i] ↔ arr[hi], the pivot stays parked at the end and the returned index lies.
• Advancing i on every comparison. i moves only when a value is accepted into the small zone; it marks a boundary, not a scan position.
• Changing the guard to <= casually. It relocates every equal-to-pivot value to the left zone — a different partition with different balance, not a cosmetic tweak.
• Assuming stability. The values end up sorted; equal elements' original order does not survive. Use merge sort when identity order matters.