Quick sort

Video walkthroughs

Two partitioning methods, each in horizontal and vertical formats. Russian subtitles are available on YouTube.

Pivot and active range

The frame marks [start, end), with an exclusive right boundary. Purple p is the last element chosen as pivot. Yellow j scans the other elements; cyan i marks the next place for a smaller value.

The initial array contains ten items, including duplicates. Letters distinguish equal values so you can track their order.

Lomuto partition invariant

Before each comparison, [start, i) is strictly smaller than the pivot, [i, j) has been checked and is not smaller, and [j, end − 1) remains unchecked. The pivot stays at end − 1.

When a[j] < pivot, swap a[i] with a[j] and advance i. Advance j after each check. Finally move the pivot to i: values on the left are smaller, those on the right are not smaller. The pivot is final, but the two sides still need sorting.

Why it is unstable

Try [2, 2]. The pivot is 2b. Since 2a is not smaller, boundary i stays at the start. The final swap produces [2b, 2a]: sorted values, but reversed original order.

Green positions are final. Unlike merge sort, a distant swap does not preserve the relative order of equal items.

Time, memory and counters

Balanced partitions take Θ(n log n). The average over random permutations of distinct values is Θ(n log n), but a fixed last-element pivot offers no guarantee. Sorted, reverse-sorted and all-equal arrays take n(n − 1)/2 comparisons and Θ(n²) time in this implementation.

Partitioning is in place. Direct recursion uses O(log n) stack space for balanced partitions and O(n) in the worst case. The wrapper copies the input using O(n) memory. Visualization history is separate: up to O(n²) snapshots of O(n) data require up to O(n³) memory. Input is limited to 24 items.

Comparisons count only value-to-pivot checks. Swaps count only exchanges between different positions, including exchanges of equal values. Assignments and pointer updates are not counted separately.

JavaScript implementation

This returns a new array using the same strict comparison and last-element pivot as the player. Events and snapshots are omitted. Self-swaps in this compact code do not affect the result.

function quickSort(values) {
    const result = [...values];
    function sort(start, end) {
        if (end - start < 2) return;
        const pivot = result[end - 1];
        let boundary = start;
        for (let scan = start; scan < end - 1; scan++) {
            if (result[scan] < pivot) {
                [result[boundary], result[scan]] = [result[scan], result[boundary]];
                boundary++;
            }
        }
        [result[boundary], result[end - 1]] = [result[end - 1], result[boundary]];
        sort(start, boundary);
        sort(boundary + 1, end);
    }
    sort(0, result.length);
    return result;
}

Comparison with other sorts

Merge sort guarantees Θ(n log n) and stability but requires a buffer. This quick sort can take Θ(n²) and is unstable. A random pivot reduces dependence on input order, but alone does not fix this partition's all-equal worst case.

For many duplicates, a three-way partition into smaller, equal and greater values is useful. That variant is available in the player selector and explained below.

Try it yourself

Compare the default array with sorted, reversed and all-equal inputs. Count comparisons and watch i and j. Try [2, 2] to observe instability. Empty and single-element inputs need no comparisons or swaps.

Three-way partition: smaller, equal, greater

Select Three-way and try Example with duplicates or All equal. Both variants choose the last value in the active range; the three-way version saves that value before swapping. The original pivot item may move, but the saved pivot value stays unchanged.

Before each check, [start, lt) < pivot; [lt, i) = pivot; [i, gt) is unchecked; [gt, end) > pivot. For a smaller item, swap a[lt] and a[i], then advance both pointers. For a greater item, decrement gt and swap a[i] with a[gt] without advancing i: the incoming item has not been checked. For an equal item, only advance i.

When i = gt, no unchecked items remain. The entire equal band [lt, gt) is final; recursion only processes smaller and greater parts. For n ≥ 2 equal items this uses 2n checks (< and then > for each item), zero swaps and one partition. Lomuto uses n(n − 1)/2 comparisons. Fewer checks on every input are not guaranteed: for 2 or 3 equal items Lomuto performs fewer checks despite its quadratic growth.

Average time over random permutations of distinct values is Θ(n log n); poor pivots can still cause Θ(n²). Stack and history costs remain separate, as in Lomuto. This algorithm is still unstable: [2, 2, 1] reverses the original order of the twos.

function threeWayQuickSort(values) {
    const result = [...values];
    function sort(start, end) {
        if (end - start < 2) return;
        const pivot = result[end - 1];
        let less = start, scan = start, greater = end;
        while (scan < greater) {
            if (result[scan] < pivot) {
                [result[less], result[scan]] = [result[scan], result[less]];
                less++;
                scan++;
            } else if (result[scan] > pivot) {
                greater--;
                [result[scan], result[greater]] = [result[greater], result[scan]];
                // Recheck the incoming item; do not advance scan.
            } else {
                scan++;
            }
        }
        sort(start, less);
        sort(greater, end);
    }
    sort(0, result.length);
    return result;
}