The Quicksort Algorithm

Bubble sort, insertion sort, and selection sort are all O(n²): double the input, and the work roughly quadruples. Quicksort takes a fundamentally different strategy — instead of scanning the whole list repeatedly, it splits the problem in half (roughly) and recurses, landing at O(n log n) on average — the same complexity class as merge sort, but usually faster in practice because it needs no extra array to do it.

The idea

Pick one element from the list — the pivot — and rearrange everything else around it so that every value smaller than the pivot ends up to its left, and every value larger ends up to its right. This step is called partitioning. Once it is done, the pivot itself is in its final, correct position: nothing will ever move past it again.

That leaves two smaller, independent problems: sort everything left of the pivot, and sort everything right of it. Solving both the same way — pick a pivot, partition, recurse — is what turns one partition into a full sort. In the best and average case, each partition roughly halves the list, so the recursion is only log n levels deep; multiplied by the O(n) cost of each level's partitioning, that gives O(n log n) overall.

Implementation

#include "plot.hpp"
#include <stdlib.h>

const int N = 20;
int values[N];
bool settled[N];

// Explicit stack instead of real recursion, so a single partitioning step
// can happen per animation tick instead of the whole sort running at once.
int stackLo[64];
int stackHi[64];
int top = -1;

int lo, hi, pivotIdx, i, j;
bool partitioning = false; // false = need the next range from the stack
bool done = false;
int tick = 0;

void push(int a, int b) {
    if (a <= b) {
        top++;
        stackLo[top] = a;
        stackHi[top] = b;
    }
}

void setup() {
    PlotCanvas(640, 480);

    for (int n = 0; n < N; n++) {
        values[n] = n + 1;
        settled[n] = false;
    }

    srand(1);
    for (int n = N - 1; n > 0; n--) {
        int r = rand() % (n + 1);
        int tmp = values[n];
        values[n] = values[r];
        values[r] = tmp;
    }

    push(0, N - 1);
}

void frame() {
    // Slow the animation down: one step every few calls to frame() instead
    // of one per call, so individual comparisons stay visible.
    if (!done && ++tick >= 4) {
        tick = 0;

        if (!partitioning) {
            if (top < 0) {
                done = true;
            } else {
                lo = stackLo[top];
                hi = stackHi[top];
                top--;
                if (lo == hi) {
                    settled[lo] = true; // single element: already in place
                } else {
                    pivotIdx = hi; // Lomuto partition: last element is the pivot
                    i = lo - 1;
                    j = lo;
                    partitioning = true;
                }
            }
        } else if (j < hi) {
            if (values[j] < values[pivotIdx]) {
                i++;
                int tmp = values[i];
                values[i] = values[j];
                values[j] = tmp;
            }
            j++;
        } else {
            i++;
            int tmp = values[i];
            values[i] = values[hi];
            values[hi] = tmp;
            settled[i] = true; // pivot has reached its final position
            push(i + 1, hi);
            push(lo, i - 1);
            partitioning = false;
        }
    }

    PlotBackground(250, 250, 250);

    int barWidth = plot_width / N;
    for (int idx = 0; idx < N; idx++) {
        if (!done && partitioning && idx == pivotIdx) {
            PlotColor(220, 60, 60);   // current pivot
        } else if (settled[idx]) {
            PlotColor(70, 170, 90);   // in its final position
        } else {
            PlotColor(30, 100, 200);  // not yet settled
        }

        int height = values[idx] * (plot_height - 20) / N;
        int x0 = idx * barWidth + 1;
        int x1 = x0 + barWidth - 2;
        int y0 = plot_height - height;
        int y1 = plot_height;
        PlotFilledRectangle(x0, y0, x1, y1);
    }
}

Real recursion would call a function for each half and let the call stack track pending work, but that runs to completion in a single call instead of one visible step at a time. The sample keeps an explicit stack of (lo, hi) ranges instead, so frame() can perform one partitioning comparison per step and still pick up exactly where it left off next time.

This uses the Lomuto partition scheme: the pivot is always the last element of the current range (values[hi]). j scans the range; whenever it finds a value smaller than the pivot, that value gets swapped just past i, which marks the boundary of everything confirmed smaller so far. Once j reaches the pivot, one last swap puts the pivot right after that boundary — its final position — and both halves get pushed onto the stack for later.

• blue — not yet in its final position
• red — the pivot of the range currently being partitioned
• green — settled in its final position

Walking through an example

Partitioning [5, 1, 4, 2, 8] with pivot 8 (the last element) is a short example, since 8 is already the largest — everything ends up on its left and the pivot does not move. A more typical case is [4, 2, 8, 5, 1] with pivot 1:

Nothing was smaller than 1, so i never advanced past lo - 1. The final swap places the pivot at index 0: [1, 2, 8, 5, 4] — note the other elements also moved, since the earlier no-op comparisons still count as j advancing past them unchanged. The pivot 1 is now correctly at the very front, with the (still unsorted) remainder [2, 8, 5, 4] to its right, ready for its own, independent partitioning step.

Why the pivot choice matters

Quicksort's O(n log n) average case assumes each partition splits the list roughly in half. The sample always picks the last element as pivot, which is simple but has a weakness: on a list that is already sorted (or reverse-sorted), that pivot is always the largest or smallest remaining value, so one side of the partition is empty every time. That degrades to n levels of recursion instead of log n, each doing O(n) work — O(n²) overall, no better than the simple sorts. Production implementations avoid this by picking the pivot differently: a random element, the median of a few sampled elements, or (as in introsort, used by most std::sort) falling back to heapsort once the recursion goes suspiciously deep.

Unlike merge sort, quicksort needs no auxiliary array — partitioning works in place — which is the main reason it tends to win in practice despite sharing the same average-case complexity.

Conclusion

Where the simple sorts all do a fixed, quadratic amount of comparison work regardless of structure, quicksort's divide-and-conquer approach turns sorting n elements into log n rounds of O(n) partitioning — as long as the pivot choice keeps the halves roughly balanced. That trade — a worst case that depends on input order, in exchange for a much better typical case — is the same idea behind most O(n log n) sorting algorithms, and quicksort remains one of the clearest ways to see it in action.