The Hidden Complexity of Quicksort

I had already solved the problem using merge sort, but I wanted to give it another shot with quicksort.

LeetCode 912,* Sort an Array*, is tagged with eight topic hints: Array, Divide and Conquer, Merge Sort, Heap, Bucket Sort, Radix Sort, Counting Sort, and Sorting**. Quicksort isn’t one of them. That should have been my first clue.

At the time, I was studying quicksort in depth. I didn’t just want to know how it worked; I wanted to understand why it worked, where it failed, and what separated a textbook implementation from one that could survive real inputs. So instead of using merge sort like I already had, I decided to force a quicksort solution through. How difficult could it be?

I expected it to be a simple exercise. It wasn’t.

I started with Lomuto partition. TLE. Switched to Hoare. TLE. Went back to Lomuto and began stacking optimizations: randomized pivot selection, tail-call elimination, insertion sort for tiny partitions. Still TLE. Every failed submission sent me further down the rabbit hole, into how Java’s Arrays.sort() is implemented, why Lomuto and Hoare behave differently on duplicate-heavy arrays, and the subtle distinction between average-case performance and expected-case performance. I reached 20 out of 21 test cases before hitting a wall I couldn't immediately explain.

Eventually, the solution passed.

But by then, getting Accepted wasn’t the interesting part anymore.

The real value came from understanding why each version failed, what every optimization actually changed, and how algorithmic guarantees interact with adversarial test cases. The exercise stopped being about solving LeetCode 912 and became an exploration of quicksort itself.

What follows is everything I learned while trying to make a handwritten quicksort implementation survive a problem that heavily rewards more robust sorting strategies, and why that detour ended up teaching me far more than the accepted submission ever could.

Starting Point — The Textbook Implementation

Most resources teach you Lomuto partition. It’s clean, intuitive, and easy to trace:

public static int lomutoPartition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr, i + 1, high);
    return i + 1;
}

Pick the last element as pivot. Walk through the array. Anything smaller than the pivot goes to the left partition. At the end, drop the pivot into place. Return its index. Recurse on both sides.

At first glance, everything seems complete. In reality, this is only the starting point of understanding quicksort.

The Practical Limits of Quicksort

Quicksort’s average case is O(n log n). Its worst case is O(n²). The gap between those two isn’t just theoretical; it’s a cliff edge.

When does it fall off?

When the pivot consistently partitions the array badly. If you always pick the last element as pivot on an already-sorted array, every partition produces one side of size 0 and another of size n-1. The recursion tree becomes a straight line. You’ve just written a very slow loop.

[1, 2, 3, 4, 5]  →  pivot = 5  →  left = [1,2,3,4], right = []
[1, 2, 3, 4]     →  pivot = 4  →  left = [1,2,3],   right = []
...

That’s O(n²). And it’s not a rare edge case. Sorted input, reverse-sorted input, and arrays with many duplicates are all extremely common in the real world.

Optimization 1 — Randomized Pivot

The fix is one line: before partitioning, swap a randomly chosen element into the pivot position.

int randIndex = low + rand.nextInt(high - low + 1);
swap(arr, randIndex, high);
// rest of partition unchanged

Why does this work? Because an adversary can no longer construct a bad input specifically for your pivot strategy. The worst case still exists mathematically, but the probability of encountering it across all recursive calls becomes vanishingly small.

For every fixed input, randomized pivot selection gives quicksort an expected running time of O(n log n), where the expectation is over the algorithm’s own random choices.

Optimization 2 — Tail Call Elimination

After partitioning, quicksort makes two recursive calls. On skewed partitions, one of those calls might be on an array of size n-1. That’s a stack depth of O(n) — a stack overflow waiting to happen on large inputs.

The key insight: the second recursive call is a tail call. Nothing happens after it returns. You can replace it with a loop.

But there’s a trick: always recurse into the smaller partition and loop into the larger one.

public static void quicksort(int[] arr, int low, int high) {
    while (low < high) {
        int pivotIndex = partition(arr, low, high);
      if (pivotIndex - low < high - pivotIndex) {
            quicksort(arr, low, pivotIndex - 1);  // recurse - smaller half
            low = pivotIndex + 1;                 // loop - larger half
        } else {
            quicksort(arr, pivotIndex + 1, high); // recurse - smaller half
            high = pivotIndex - 1;                // loop - larger half
        }
    }
}

Why does the smaller-first rule matter? Because the smaller half is at most n/2. It can only halve log n times. So the recursive call stack depth is bounded at O(log n), roughly 20 frames for a million elements, instead of potentially a million frames.

Optimization 3 — Insertion Sort Cutoff

For small subarrays, quicksort’s overhead, including function calls, partitioning, and pivot selection, often outweighs its benefits. In contrast, insertion sort has almost no overhead, exhibits excellent cache behavior, and runs in O(n) time on nearly sorted data. By the time quicksort reaches these tiny partitions, they are often already close to sorted, making insertion sort the faster choice in practice.

private static final int INSERTION_THRESHOLD = 10;
if (high - low < INSERTION_THRESHOLD) {
    insertionSort(arr, low, high);
    break;
}

Java’s Arrays.sort() uses a similar optimization internally, switching to insertion sort for sufficiently small partitions.

What Java’s Arrays.sort Actually Does

This is where it gets interesting for Java developers specifically.

Arrays.sort doesn't use a single algorithm. It uses two completely different implementations depending on what you're sorting:

                    Arrays.sort()
                          │
          ┌───────────────┴───────────────┐
          │                               │
          ▼                               ▼
   Primitive Arrays                Object Arrays
(int[], long[], etc.)      (Integer[], String[], etc.)
          │                               │
          ▼                               ▼
 Dual-Pivot Quicksort                  TimSort
          │                               │
          ▼                               ▼
Optimized for speed             Stable sort preserves
Stability not required       the order of equal elements

Object arrays require a stable sort so that equal elements preserve their relative order. Primitive arrays have no such requirement, allowing Java to use dual-pivot quicksort instead.

Java’s Dual-Pivot Quicksort, introduced in Java 7 and engineered by Vladimir Yaroslavskiy, uses two pivots instead of one:

[ < p1 | p1 <= x <= p2 | > p2 ]

Three partitions instead of two. This reduces the average number of comparisons and produces better branch prediction patterns on modern CPUs. And dual-pivot is just one of its improvements. Modern implementations also include insertion sort cutoffs, special handling for nearly sorted sequences, and other refinements that go well beyond pivot selection. It’s one of the most carefully engineered pieces of code in any standard library.

When you call Arrays.sort(int[] arr), you are running a descendant of everything we've been discussing.

Time Limit Exceeded — The 21st Test Case

I submitted with all three optimizations in place. 20/21.

The judge reported the last executed input as [110, 100, 0], a three-element array. But that wasn't the input causing the slowdown. It was simply the last test case displayed before termination. The real bottleneck was a much larger hidden test case, and the TLE pointed to something that randomization alone couldn't fix. Even with a random pivot, arrays containing many duplicate values can still produce highly unbalanced partitions under Lomuto's scheme.

The feedback made it explicit:

Switch to Hoare partition or fix Lomuto logic to handle duplicates efficiently.

Lomuto’s Hidden Weakness — Duplicates

Lomuto partition has a structural flaw with duplicate elements. The condition arr[j] <= pivot means equal elements always cross to the left partition. On an array full of duplicates, the pivot consistently lands near one end, producing a 0/n-1 split. You're back to O(n²).

Hoare partition generally performs much better than Lomuto on duplicate-heavy arrays because equal elements are less likely to accumulate on one side of the partition — the two pointers move past them from both ends rather than always pushing them left. It’s not a perfect solution for duplicates (three-way partitioning handles that case optimally), but it’s a significant structural improvement over Lomuto for this scenario.

public static int hoarePartition(int[] arr, int low, int high) {
    int randIndex = low + rand.nextInt(high - low + 1);
    swap(arr, randIndex, low);       // pivot goes to low, not high
    int pivot = arr[low];
    int i = low - 1;
    int j = high + 1;
    while (true) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        if (i >= j) return j;
        swap(arr, i, j);
    }
}

The critical difference from Lomuto: Hoare doesn’t place the pivot at its final sorted position. After partition, the pivot is somewhere in arr[low..j]. So recursion calls change:

// Lomuto
quicksort(arr, low, pivotIndex - 1);
quicksort(arr, pivotIndex + 1, high);
// Hoare - note: j not j-1 on the left side
quicksort(arr, low, pivotIndex);
quicksort(arr, pivotIndex + 1, high);

Getting this boundary wrong is the most common Hoare bug. The pivot is not guaranteed to be at index j — it could be anywhere in the left partition.

With Hoare partition: Accepted.

The Full Comparison

                 Partition Schemes
                        │
          ┌─────────────┴─────────────┐
          │                           │
          ▼                           ▼
       Lomuto                      Hoare
          │                           │
 ┌────────┼─────────┐      ┌──────────┼─────────┐
 │        │         │      │          │         │
 ▼        ▼         ▼      ▼          ▼         ▼
Pivot   More     Can     Pivot      Fewer    Better with
fixed   swaps   skew on  not fixed  swaps    duplicates
                duplicates

The Takeaway

My quicksort implementation was correct and heavily optimized. The TLE wasn’t caused by a bug in the code. It was a limitation of the underlying partition scheme. Under certain stress conditions, particularly with many duplicate values, Lomuto’s partitioning can still produce highly unbalanced partitions because of the way it handles elements equal to the pivot.

The journey, laid out honestly:

Each step addressed a real failure mode. The randomized pivot defeated sorted and reverse-sorted inputs. Tail call elimination capped the stack depth at O(log n). The insertion sort cutoff eliminated overhead on small subarrays. And Hoare partition fixed the structural weakness that Lomuto has always had with duplicate-heavy data.

Understanding why each one exists is what separates knowing quicksort from understanding it.

For Java developers specifically: when you call Arrays.sort on a primitive array, you're running a more sophisticated version of this exact journey. Yaroslavskiy's dual-pivot implementation is what happens when you take these ideas seriously at production scale.

The textbook version of quicksort is only the beginning.

Production implementations spend as much effort avoiding pathological cases as they do implementing the partition itself. Studying those edge cases taught me more about algorithm engineering than getting an Accepted submission ever could.