Quick Sort

Quick Sort

Quicksort is the most important sorting algorithm for technical interviews. It appears on whiteboards and coding screens more than any other sort, it forms the foundation of Java’s Arrays.sort for primitives, and its partitioning logic extends to selection, sampling, and database query processing. If you master one sorting algorithm end-to-end, make it this one.

The Algorithm

Quicksort follows a divide-and-conquer strategy:

1. Choose a pivot element from the array.
2. Partition the array: rearrange elements so that all elements less than the pivot come before it, and all elements greater come after it. The pivot is now in its final sorted position.
3. Recurse on the two sub-arrays: the elements before the pivot and the elements after it.

The recursion terminates when sub-arrays have zero or one element — they are trivially sorted.

The magic of quicksort lies in the partitioning step. After partitioning, the pivot never moves again. Each recursive call places one more element (the pivot) in its final position and reduces the problem size. Unlike merge sort, which does its work during the merge phase, quicksort does its work during the partition phase — the combining step is free.

Lomuto Partition Scheme

The Lomuto partition scheme is the simpler of the two major approaches. It uses the last element as the pivot and maintains a single scan pointer.

How It Works

Maintain an index i that tracks the boundary of elements less than the pivot. Scan through the array with index j. Whenever arr[j] < pivot, swap arr[j] with arr[i + 1] and increment i. After the scan, swap the pivot (at the end) with arr[i + 1].

Java 25 Implementation

void quickSortLomuto(int[] arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partitionLomuto(arr, low, high);
        quickSortLomuto(arr, low, pivotIndex - 1);
        quickSortLomuto(arr, pivotIndex + 1, high);
    }
}

int partitionLomuto(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++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // Place pivot in its correct position
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

Walkthrough

Sorting [3, 6, 8, 10, 1, 2, 1] with Lomuto (pivot = 1 at end):

pivot = 1, i = -1

j=0: arr[0]=3 > 1   → skip
j=1: arr[1]=6 > 1   → skip
j=2: arr[2]=8 > 1   → skip
j=3: arr[3]=10 > 1  → skip
j=4: arr[4]=1 ≤ 1   → i=0, swap arr[0] and arr[4] → [1, 6, 8, 10, 3, 2, 1]
j=5: arr[5]=2 > 1   → skip

Swap pivot: arr[1] and arr[6] → [1, 1, 8, 10, 3, 2, 6]
Pivot index = 1

Now 1 is at index 1 — its final sorted position. Recurse on [1] (left) and [8, 10, 3, 2, 6] (right).

Lomuto’s Weakness

Lomuto has two problems:

1. O(n²) on already-sorted arrays: When the last element is always the smallest or largest, every partition produces sub-arrays of size 0 and n-1. The recursion has depth n, and each level does O(n) work: total O(n²).
2. Poor with duplicates: All elements equal to the pivot go to one side. An array of identical elements triggers O(n²) behavior.

These weaknesses are fixable — via pivot selection strategies and three-way partitioning.

Hoare Partition Scheme

Tony Hoare’s original partition scheme (1962) uses two pointers that start at opposite ends and move inward. It is more efficient than Lomuto in practice — roughly three times fewer swaps on average.

How It Works

Choose a pivot (typically the first element). Set pointer i at the start and pointer j at the end. Move i right until finding an element ≥ pivot. Move j left until finding an element ≤ pivot. If i < j, swap them. Repeat until the pointers cross.

Java 25 Implementation

void quickSortHoare(int[] arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partitionHoare(arr, low, high);
        quickSortHoare(arr, low, pivotIndex);
        quickSortHoare(arr, pivotIndex + 1, high);
    }
}

int partitionHoare(int[] arr, int low, int 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;
        }
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Critical Differences from Lomuto

Property	Lomuto	Hoare
Pivot position after partition	Pivot is in its final place	Pivot is NOT necessarily in its final place
Recursive calls	(low, p-1) and (p+1, high)	(low, p) and (p+1, high)
Average swaps	~n/2	~n/6
Behavior on sorted input	O(n²) with last-element pivot	O(n²) with first-element pivot

The Hoare scheme’s return value j marks the boundary between the two partitions, but the pivot element can end up anywhere in the left partition. This means you recurse on (low, j) including the boundary — not (low, j-1).

Common bug: Using (low, pivotIndex - 1) with Hoare partition. This skips elements and produces incorrect results. Always use (low, pivotIndex) with Hoare.

Pivot Selection Strategies

The choice of pivot determines quicksort’s performance. A good pivot splits the array roughly in half; a bad pivot creates lopsided partitions.

Fixed Pivot (First or Last Element)

• Problem: Sorted or nearly-sorted input causes O(n²) behavior. The first element is the minimum (or the last is the maximum), so every partition splits into sizes 0 and n-1.
• When it’s acceptable: Random input only. Never use fixed pivots in production.

Random Pivot

Select a random index in [low, high] and swap that element with the partition position before partitioning.

int randomizedPartition(int[] arr, int low, int high) {
    int randomIndex = low + ThreadLocalRandom.current().nextInt(high - low + 1);
    // Swap random element to last position for Lomuto
    int temp = arr[randomIndex];
    arr[randomIndex] = arr[high];
    arr[high] = temp;
    return partitionLomuto(arr, low, high);
}

• Expected time: O(n log n) on all inputs. The probability of consistently picking bad pivots is exponentially small.
• Worst case: Still O(n²), but the probability is $O(1/n!)$ — practically impossible.
• Trade-off: Random number generation has a small cost per partition call.

Median-of-Three

Pick three elements — arr[low], arr[mid], arr[high] — and use the median of these three as the pivot.

int medianOfThree(int[] arr, int low, int high) {
    int mid = low + (high - low) / 2;
    // Sort the three elements
    if (arr[low] > arr[mid]) swap(arr, low, mid);
    if (arr[low] > arr[high]) swap(arr, low, high);
    if (arr[mid] > arr[high]) swap(arr, mid, high);
    // Median is now at arr[mid] — swap to partition position
    swap(arr, mid, high - 1);
    return partitionLomuto(arr, low + 1, high - 1);
}

void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

• Eliminates O(n²) on sorted input: The median of (first, middle, last) of a sorted array is the middle element — a perfect pivot.
• No randomization cost: Deterministic and reproducible.
• Industry standard: This is the pivot strategy used in most production quicksort implementations.

Pivot Strategy Summary

Strategy	Sorted Input	Random Input	Duplicates
Fixed (last)	O(n²)	O(n log n) expected	O(n²)
Random	O(n log n) expected	O(n log n) expected	O(n²)
Median-of-Three	O(n log n)	O(n log n)	O(n²)

Notice that none of these strategies handle duplicate-heavy input well. That’s where three-way partitioning comes in.

Three-Way Partition (Dutch National Flag)

When the array contains many duplicate elements, standard quicksort degenerates to O(n²). Every element equal to the pivot ends up on one side, creating extreme imbalance when most elements share the same value.

The solution: three-way partitioning, also known as the Dutch National Flag algorithm (after Dijkstra’s formulation). Instead of two regions (< pivot, > pivot), create three:

[ < pivot | == pivot | > pivot ]

Elements equal to the pivot are already in their final positions — no recursion needed on them. For an array of all equal elements, three-way partition runs in O(n) instead of O(n²).

Java 25 Implementation

void quickSort3Way(int[] arr, int low, int high) {
    if (low >= high) return;

    int pivot = arr[low];
    int lt = low;      // arr[low..lt-1]  < pivot
    int gt = high;     // arr[gt+1..high] > pivot
    int i = low + 1;   // arr[lt..i-1]   == pivot (scanning pointer)

    while (i <= gt) {
        if (arr[i] < pivot) {
            swap(arr, lt, i);
            lt++;
            i++;
        } else if (arr[i] > pivot) {
            swap(arr, i, gt);
            gt--;
            // Don't increment i — swapped element needs inspection
        } else {
            i++;  // arr[i] == pivot — extend equal region
        }
    }

    // Recurse on < and > regions only — equals are done
    quickSort3Way(arr, low, lt - 1);
    quickSort3Way(arr, gt + 1, high);
}

Walkthrough

Sorting [4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4] (many duplicates, pivot = 4):

After partitioning:

[1, 1 | 4, 4, 4, 4, 4, 4, 4 | 9, 9, 9]
 <4     ==4                    >4

Recurse on [1, 1] (trivial) and [9, 9, 9] (trivial). The seven 4s never move again. Total work: O(n) for this input.

When to Use Three-Way

• Arrays with many duplicate keys (database columns with categorical data).
• Sorting by bucketed or binned values.
• Any scenario where the key space is smaller than the array size.

Quickselect: Finding the kth Element

Quicksort’s partitioning logic solves another interview classic: finding the kth smallest element without sorting the entire array.

After partitioning, the pivot is at index p. If p == k, you’ve found the answer. If k < p, recurse on the left partition only. If k > p, recurse on the right partition only. You discard half the array each time (on average), yielding O(n) expected time.

Java 25 Implementation

int quickSelect(int[] arr, int low, int high, int k) {
    if (low == high) {
        return arr[low];
    }

    int pivotIndex = randomizedPartition(arr, low, high);

    if (k == pivotIndex) {
        return arr[k];
    } else if (k < pivotIndex) {
        return quickSelect(arr, low, pivotIndex - 1, k);
    } else {
        return quickSelect(arr, pivotIndex + 1, high, k);
    }
}

// Usage: find kth smallest (0-indexed)
int kthSmallest = quickSelect(arr, 0, arr.length - 1, k);

Complexity

Metric	Value
Expected time	O(n)
Worst-case time	O(n²) — bad pivots every time
Space	O(log n) expected — recursion stack

Use randomized pivot selection to make the O(n²) case vanishingly improbable. The median-of-medians algorithm guarantees O(n) worst case but has large constants — it’s rarely used in practice.

Interview applications: “Find the kth largest element” (LeetCode #215), “Find the median of an unsorted array”, “Find the top-k elements”. These are staple interview questions, and quickselect is the expected O(n) solution.

Full Complexity Analysis

Time Complexity

Best case — O(n log n): Each partition splits the array in half. Recursion depth is log₂(n), and each level does O(n) total work across all partitions:

$$T(n) = 2T(n/2) + O(n) = O(n \log n)$$

Average case — O(n log n): Even imperfect splits like 90/10 yield O(n log n). The expected number of comparisons is approximately $1.39 \cdot n \log_2 n$ — about 39% more comparisons than merge sort, but quicksort’s better cache performance and lower constant factor make it faster in practice.

Worst case — O(n²): Every partition produces sub-arrays of size 0 and n-1. This happens with sorted input + fixed pivot, or all-equal elements without three-way partitioning:

$$T(n) = T(n-1) + O(n) = O(n^2)$$

Space Complexity

O(log n) average — The recursion stack depth equals the number of nested recursive calls. With balanced partitions, the depth is log₂(n).

O(n) worst case — Unbalanced partitions produce recursion depth n. Tail-call optimization (covered below) addresses this.

Stability

Quicksort is NOT stable. Partitioning swaps elements across long distances, disrupting the relative order of equal elements. Making quicksort stable requires O(n) extra space — at which point, merge sort is a better choice.

Summary Table

Metric	Value
Best time	O(n log n)
Average time	O(n log n)
Worst time	O(n²)
Average space	O(log n)
Worst space	O(n)
Stable	No
In-place	Yes (ignoring recursion stack)

Tail-Call Optimization

Standard quicksort makes two recursive calls. The second call can be replaced with a loop (tail-call elimination), and by always recursing on the smaller partition, you guarantee the stack depth never exceeds O(log n) — even for worst-case inputs.

void quickSortTailOptimized(int[] arr, int low, int high) {
    while (low < high) {
        int pivotIndex = partitionLomuto(arr, low, high);

        // Recurse on the smaller partition, iterate on the larger
        if (pivotIndex - low < high - pivotIndex) {
            quickSortTailOptimized(arr, low, pivotIndex - 1);
            low = pivotIndex + 1;  // Iterate on right (larger) partition
        } else {
            quickSortTailOptimized(arr, pivotIndex + 1, high);
            high = pivotIndex - 1;  // Iterate on left (larger) partition
        }
    }
}

This technique keeps the recursive call on the smaller sub-array (at most n/2 elements), so the recursion depth is bounded by log₂(n). The larger sub-array is handled iteratively in the while loop.

Interview signal: Mentioning tail-call optimization demonstrates understanding of stack space management — a topic that distinguishes senior-level candidates.

Java’s Arrays.sort for Primitives: Dual-Pivot Quicksort

Since Java 7, Arrays.sort(int[]) uses dual-pivot quicksort (Yaroslavskiy’s algorithm). Instead of one pivot, it uses two pivots that create three partitions:

[ < pivot1 | pivot1 ≤ x ≤ pivot2 | > pivot2 ]

This reduces the average number of comparisons to approximately $1.9n \ln n$ (compared to $2n \ln n$ for single-pivot quicksort) and demonstrates better cache locality. The implementation in java.util.DualPivotQuicksort also incorporates:

• Insertion sort for arrays below 47 elements.
• Counting sort for byte, short, and char arrays.
• Merge sort fallback when the array is detected to be highly structured.

You don’t need to implement dual-pivot quicksort in an interview, but knowing that Java uses it — and why — shows applied knowledge.

Interviewer Tips

Quicksort is the #1 most-asked sorting algorithm. Be prepared to implement it from scratch, explain partitioning, analyze complexity, and discuss pivot selection — all under time pressure.

Default to Lomuto for whiteboard coding. It’s simpler to implement correctly under pressure. Mention Hoare’s scheme as a more efficient alternative and offer to implement it if the interviewer wants to see it.

Always address the O(n²) worst case. An interviewer who asks “What’s quicksort’s worst case?” expects you to explain why it happens (bad pivot selection on sorted input) and how to fix it (random pivot, median-of-three). Going straight from “O(n²) worst case” to “use randomized pivots for expected O(n log n)” demonstrates problem-solving depth.

Know three-way partitioning for the duplicates question. “What happens if all elements are equal?” is a classic follow-up. Answer: “Standard quicksort degrades to O(n²). Three-way partitioning with the Dutch National Flag algorithm handles this in O(n) by grouping equal elements together.”

Have quickselect ready. “Find the kth largest element” is a top-30 interview question. The expected answer is quickselect with randomized pivots in O(n) expected time. Walk through the partition-and-recurse logic to show you understand it, not as a memorized formula.

Compare quicksort and merge sort. Interviewers love this question:

• Quicksort: In-place, O(n log n) average, O(n²) worst case, not stable, better cache performance.
• Merge sort: O(n) extra space, O(n log n) guaranteed, stable, worse cache performance.
• Production systems use quicksort for primitives (where stability doesn’t matter) and merge sort (via TimSort) for objects (where stability matters).