Quick Sort

The idea

Quick sort is another divide-and-conquer algorithm, but it does the hard work before recursing instead of after:

1. Pick a pivot — here, the last element.
2. Partition: rearrange the array so everything ≤ pivot is on its left and everything > pivot is on its right. The pivot is now in its final position.
3. Recurse on the left part and the right part.

No merging is needed — when the recursion finishes, the array is sorted.

Analogy: a teacher sorting students by height picks one student (the pivot) and says “shorter than her, stand on the left; taller, on the right”. She is now in exactly the right spot. Repeat inside each group.

Lomuto partition, step by step

We scan with j from lo to hi − 1, and i marks the end of the “≤ pivot” zone:

pivot = a[hi]
i = lo - 1
for j in lo .. hi-1:
    if a[j] <= pivot:
        i += 1
        swap(a[i], a[j])        # grow the ≤ zone
swap(a[i+1], a[hi])             # put the pivot between the zones
return i + 1                    # the pivot's final index

At every moment the range looks like this:

In the 3D model the pivot steps forward out of the row while the partition happens, and drops back into its final slot at the end.

Why is it fast — and when isn’t it?

If the pivot splits the array roughly in half each time, there are about log₂ n levels of recursion, each doing O(n) work in total → O(n log n).

But if the pivot is always the smallest or largest element, one side gets everything: n levels of O(n) → O(n²). With “last element as pivot”, this happens on already sorted data — try it in the model!

Fixes used in practice:

• Random pivot — swap a random element into the pivot position first.
• Median-of-three — use the median of the first, middle and last elements.
• Introsort (C++ std::sort) — switch to heap sort if the recursion gets too deep.

Even so, quick sort is often the fastest sort in practice: it works in-place and its inner loop is very cache-friendly.

Code

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

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

print(quick_sort([10, 80, 30, 90, 40, 50, 70]))   # [10, 30, 40, 50, 70, 80, 90]

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

int partition(vector<int>& a, int lo, int hi) {
    int pivot = a[hi], i = lo - 1;
    for (int j = lo; j < hi; j++)
        if (a[j] <= pivot) swap(a[++i], a[j]);
    swap(a[i + 1], a[hi]);
    return i + 1;
}

void quickSort(vector<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);
}

int main() {
    vector<int> a = {10, 80, 30, 90, 40, 50, 70};
    quickSort(a, 0, a.size() - 1);
    for (int x : a) cout << x << " ";   // 10 30 40 50 70 80 90
}

Quick sort vs merge sort

Common mistakes

• Recursing on (lo, p) instead of (lo, p − 1) — the pivot is already placed, and including it can loop forever.
• Forgetting the final swap that moves the pivot into place.
• Assuming O(n log n) always — remember the sorted-input trap.