DSA Complexity

Quick sort cost

Product tension: the p95 latency looks great until one pathological shard hits sorted keys and a naive pivot.

Quicksort's headline is versus . In-place partition, unstable typically, stack O(log n) expected.

Algorithm journey

Linear partition

Theta(n) work per call on a range.

Pivot quality

Controls subproblem sizes.

Expectation

Random pivots imply Theta(n log n).

Depth guard

Heapsort fallback caps disasters.

What actually happens

Naive claim: "quicksort is O(n log n)." Underspecified: say average/expected vs worst.

Better claim: randomize or introspect.

Duplicates without three-way partitioning can also degrade practical performance.

Invariant

After partition, the pivot is in final position; cost sums partition work over the recursion tree, which is balanced only when pivots are.

How to read quicksort's complexity

1. Quote average and worst separately. Always.

2. Shipping a library sort? Prefer introsort-style guards.

3. Teaching? Derive the recurrence for best/avg/worst splits.

Quantitative check

n = 10^6: expected ~ 2n ln n ≈ 2.8e7 comparisons with random pivots; worst ~ n^2/2 ≈ 5e11. That gap is the whole point of the guardrail discussion.

How it works

Choose a Pivot

Pick an element from the array to serve as the pivot (e.g., first, last, or random element).

Partitioning

Reorder the array so that all elements with values less than the pivot come before it, and all elements with values greater than the pivot come after it.

Recursion

Recursively apply the above steps to the sub-array of elements with smaller values and the sub-array of elements with greater values.

🎯 Visual Example

Sorting [8, 3, 1, 7, 0, 10, 2] using last element (2) as pivot:

Step 1: Partition around 2

Pivot = 2

Compare elements: 8>2, 3>2, 1<2 (swap), 7>2, 0<2 (swap), 10>2

Result: [1, 0, 2, 7, 3, 10, 8]

Left sub-array: [1, 0], Right sub-array: [7, 3, 10, 8]

Step 2: Recurse Left [1, 0]

Pivot = 0

Result: [0, 1]

Step 3: Recurse Right [7, 3, 10, 8]

Pivot = 8

Result: [7, 3, 8, 10]

Sorting [7, 3] yields [3, 7], so the final array is [0, 1, 2, 3, 7, 8, 10].

🎮 Interactive Quick Sort Demo

Click "Start" to watch how the pivot partitions the array and recursively sorts the parts!

Speed:

ℹ️ Ready

Comparing/Active

Sorted

Tip: Avoid the Worst Case!

Quick Sort's Θ(n²) worst case occurs when pivots repeatedly create one-sided partitions. Sorted input triggers this for fixed first/last-pivot implementations, but not inherently for the randomized implementation below. Randomization gives expected Θ(n log n); an introspective fallback supplies a deterministic worst-case defense.

💻 Implementation

Python

python

from __future__ import annotations

from random import Random


def quick_sort(values: list[int], seed: int | None = None) -> list[int]:
    """In-place randomized three-way quicksort; returns values for convenience."""
    random = Random(seed)

    def sort_range(low: int, high: int) -> None:
        while low < high:
            pivot = values[random.randrange(low, high + 1)]

            # Dutch-national-flag partition:
            # [low, less) < pivot, [less, scan) == pivot,
            # [scan, greater] unknown, (greater, high] > pivot.
            less, scan, greater = low, low, high
            while scan <= greater:
                if values[scan] < pivot:
                    values[less], values[scan] = values[scan], values[less]
                    less += 1
                    scan += 1
                elif values[scan] > pivot:
                    values[scan], values[greater] = values[greater], values[scan]
                    greater -= 1
                else:
                    scan += 1

            # Recurse into the smaller side and loop over the larger side.
            # This caps call-stack depth at O(log n), even on bad partitions.
            if less - low < high - greater:
                sort_range(low, less - 1)
                low = greater + 1
            else:
                sort_range(greater + 1, high)
                high = less - 1

    sort_range(0, len(values) - 1)
    return values


if __name__ == "__main__":
    data = [8, 7, 2, 1, 8, 9, 6, 8]
    print(quick_sort(data, seed=42))

Java

java

public class QuickSort {
    static void quickSort(int[] values, long seed) {
        sortRange(values, 0, values.length - 1, new java.util.Random(seed));
    }

    private static void sortRange(
            int[] values, int low, int high, java.util.Random random) {
        while (low < high) {
            int pivot = values[low + random.nextInt(high - low + 1)];

            // [low, less) < pivot; [less, scan) == pivot;
            // [scan, greater] unknown; (greater, high] > pivot.
            int less = low;
            int scan = low;
            int greater = high;
            while (scan <= greater) {
                if (values[scan] < pivot) {
                    swap(values, less++, scan++);
                } else if (values[scan] > pivot) {
                    swap(values, scan, greater--);
                } else {
                    scan++;
                }
            }

            // Recurse only into the smaller side; iterate over the larger.
            if (less - low < high - greater) {
                sortRange(values, low, less - 1, random);
                low = greater + 1;
            } else {
                sortRange(values, greater + 1, high, random);
                high = less - 1;
            }
        }
    }

    private static void swap(int[] values, int left, int right) {
        int temporary = values[left];
        values[left] = values[right];
        values[right] = temporary;
    }

    public static void main(String[] args) {
        int[] data = {8, 7, 2, 1, 8, 9, 6, 8};
        quickSort(data, 42L);
        System.out.println(java.util.Arrays.toString(data));
    }
}

Partition invariant and correctness

During the three-way partition, the range is divided into values known to be less than the pivot, equal to it, unknown, and greater than it. Every iteration shrinks the unknown region by one, so partitioning terminates in Θ(m) time for a subarray of length m. Afterward the equal block is already in its final rank range.

Recursive calls touch only the disjoint less-than and greater-than regions. By induction, each becomes sorted; their ordering around the pivot block proves the whole range is sorted. Three-way partitioning also turns an all-equal input into one linear partition instead of a quadratic chain of nearly empty partitions.

Pivot and partition design space

Choice	Strength	Risk / use
Lomuto	Small, teachable loop	More swaps; one-sided on many duplicates
Hoare	Fewer swaps, good locality	Boundary convention is easier to get wrong
Three-way	Collapses duplicate keys in one pass	A little more branching; used in the code above
Random pivot	Expected Θ(n log n) independent of input order	Seed tests; adversarial guarantees still need a fallback
Median-of-three	Cheap deterministic heuristic	Crafted patterns can still defeat it

⚡ Complexity Analysis

Time Complexity

✓
Θ(n log n) - Expected Case
Random pivots give balanced recursion in expectation
✗
Θ(n²) - Worst Case
An unlucky or adversarial sequence of extreme pivots

Space Complexity

✓
O(log n)
Stack space for recursion

Other Properties

✗NOT Stable: Relative order changes
✓In-place: Minimal extra memory

✅ Pros & ❌ Cons

✅ Advantages

✓Very fast in practice (good cache locality)
✓In-place sorting (low memory usage)
✓Parallelizable (sub-arrays are independent)

❌ Disadvantages

✗Worst-case O(n²) can be disastrous
✗Not stable (bad for multi-key sorting)
✗Recursive overhead for very small arrays

Worst-case defenses and production contract

Time defense: introsort switches to heap sort when recursion depth exceeds about 2⌊log₂n⌋, guaranteeing O(n log n).
Stack defense: recurse into the smaller partition and loop over the larger one, as above. This makes stack depth O(log n) even if time degrades to Θ(n²).
Mutation: both functions rearrange the caller's array and are unstable. Copy first or choose a stable sort when the API requires those guarantees.
Runtime traps: Python's default recursion limit makes naive recursion fragile; Java can throw StackOverflowError. Avoid allocating slices or boxed temporary lists per level.
Tests: assert sortedness and multiset preservation on empty, sorted, reverse, organ-pipe, all-equal, duplicate-heavy, extreme-value, and seeded random arrays.

Expected Θ(n log n) requires randomness over pivots, not a claim that inputs are “usually random.” For untrusted input, use an introspective fallback or a library sort with a documented worst-case guarantee.

Exercises

Write recurrences for best (perfect split), worst (n-1 split), and sketch the average argument.
Show how a depth limit of 2 log2 n prevents Theta(n^2) time.
Why does "average" need a probability model over pivots or inputs?

Primary sources

CLRS: quicksort probabilistic analysis.
Hoare 1961.
Musser introsort paper.

Short takeaway

Quick Sort = Pick pivot, partition, recurse.Time: Expected Θ(n log n) with random pivots; Θ(n²) worst case.Space: O(log n) stack.Best for: In-place array partitioning and as a component of guarded hybrid sorts; prefer library sort APIs.Watch out for: deterministic bad pivots, duplicate-heavy inputs without three-way partitioning, and stack depth.