Free lesson · DSA Mastery - Interview Prep, End to End

Quick Sort

Easy10 min readdsasorting-algorithms

Quick Sort

Quick Sort is the algorithm most production sort libraries use. It is fast in practice - often the fastest of any comparison-based sort despite having a worse worst case than Merge Sort. The reasons are cache-friendliness, low constant factors, and the rarity of the worst case in practice.

The algorithm is also a great example of how divide and conquer can take an unusual shape. Where Merge Sort splits the array in half and recurses, Quick Sort uses a pivot to partition the array into two pieces: things smaller than the pivot, and things bigger. Then it recurses on each piece. The "merge" step is trivial because the partition already places the pivot in its final position.

In this chapter, we will walk through how Quick Sort works, why pivot selection matters so much, and how production implementations avoid the O(n²) worst case.

What Is Quick Sort?

Imagine you are sorting a stack of papers by date. You pick one paper at random and say "everything older than this goes in pile A, everything newer goes in pile B." After one pass, the paper you picked sits between the two piles in its correct final position. Then you sort pile A and pile B the same way, recursively.

That is Quick Sort. The paper you pick is called the pivot. The split into A and B is called the partition. The recursion handles the rest.

The strategy in plain steps:

1. If the array has 0 or 1 elements, it is already sorted. Return.
2. Pick a pivot.
3. Partition: rearrange the array so all elements less than the pivot are on the left, the pivot is in the middle, and all elements greater are on the right.
4. Recursively sort the left partition.
5. Recursively sort the right partition.

graph TD
    A["quickSort(arr, lo, hi)"] --> B{"lo >= hi?"}
    B -->|Yes| C["Return (base case)"]
    B -->|No| D["Pick a pivot"]
    D --> E["Partition around pivot"]
    E --> F["Pivot is now in<br/>its final position"]
    F --> G["quickSort(left partition)"]
    F --> H["quickSort(right partition)"]
    
    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style G fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style H fill:#4338ca,stroke:#6366f1,color:#f1f5f9

This diagram shows the structure of Quick Sort. We start with the array bounds lo and hi. If lo is greater than or equal to hi, we are at a base case and return. Otherwise, we pick a pivot, partition the array around it, and then the pivot is in its final position. We recursively sort the left partition and the right partition. The recursion bottoms out at single-element segments.

The interesting thing about Quick Sort: there is no separate "combine" step. The partition itself does all the work. Once both recursive calls return, the entire segment is sorted because the pivot was already in its final position and both halves are sorted around it.

How It Works

Let us look at the pieces.

The Partition

This is the algorithm's core operation. Given a segment of the array and a pivot value, the partition rearranges the segment so that:

• Everything less than the pivot ends up on the left.
• The pivot ends up in its final position.
• Everything greater than the pivot ends up on the right.

There are several partition schemes. The most common is Lomuto's partition, which is simpler but slightly slower. Hoare's partition is faster but trickier. For this course, we will use Lomuto's because it is easier to understand.

In Lomuto's partition, we pick the last element as the pivot, then use two pointers:

• i tracks the boundary between "elements less than pivot" and "elements greater than pivot."
• j scans through the array.

Each time we see an element less than the pivot, we swap it into the "less than" region and advance i. At the end, we put the pivot in position i (where it belongs) by swapping with arr[hi].

private static int partition(int[] arr, int lo, int hi) {
    int pivot = arr[hi];
    int i = lo - 1;
    
    for (int j = lo; j < hi; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    
    int temp = arr[i + 1];
    arr[i + 1] = arr[hi];
    arr[hi] = temp;
    
    return i + 1;
}

After this returns, arr[i + 1] holds the pivot in its final position. Everything to its left is less than the pivot; everything to its right is greater.

Pivot Selection (This Is What Matters)

Quick Sort's complexity depends entirely on how balanced the partitions are. If the pivot splits the array in half each time, we get O(n log n). If the pivot is always the smallest or largest element, the partition is maximally unbalanced (one side has n-1 elements, the other has 0), and we degrade to O(n²).

A few common pivot strategies:

• Last element (simple): Always pick arr[hi]. Fast and simple, but produces O(n²) on already-sorted input. Avoid in production.
• First element: Same problem. Avoid.
• Middle element: Pick arr[(lo + hi) / 2]. Better than first or last but still has bad cases.
• Random: Pick a random index. Statistical worst case is astronomically unlikely. Good default for production.
• Median-of-three: Pick the median of arr[lo], arr[mid], arr[hi]. Avoids degenerate behavior on sorted and nearly-sorted input.

For this course, we will use the simple "last element" pivot for clarity. Production code uses random or median-of-three.

The Full Algorithm

1. If lo >= hi, return (base case).
2. Partition the segment arr[lo..hi], returning the pivot's final index p.
3. Recursively sort arr[lo..p-1].
4. Recursively sort arr[p+1..hi].

The recursion produces a tree of calls. In the balanced case, the tree has log n levels, and each level does O(n) total work - giving O(n log n).

Code Implementation

public static void quickSort(int[] arr) {
    quickSortHelper(arr, 0, arr.length - 1);
}

private static void quickSortHelper(int[] arr, int lo, int hi) {
    if (lo >= hi) return;
    
    int p = partition(arr, lo, hi);
    quickSortHelper(arr, lo, p - 1);
    quickSortHelper(arr, p + 1, hi);
}

private static int partition(int[] arr, int lo, int hi) {
    int pivot = arr[hi];
    int i = lo - 1;
    
    for (int j = lo; j < hi; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    
    int temp = arr[i + 1];
    arr[i + 1] = arr[hi];
    arr[hi] = temp;
    
    return i + 1;
}

// Usage:
// int[] arr = {5, 2, 8, 1, 9, 3};
// quickSort(arr);
// System.out.println(Arrays.toString(arr));
// Output: [1, 2, 3, 5, 8, 9]

This Java code implements Quick Sort with Lomuto's partition scheme. The public quickSort function calls the recursive helper. The helper base-cases when lo is greater than or equal to hi, otherwise it partitions and recurses on each side of the pivot. The partition function uses the last element as the pivot, scans through the segment with two pointers, and places the pivot in its final position. After partitioning, the pivot index is returned to the helper for use in the recursive calls.

A few implementation notes:

The pivot is the last element (arr[hi]). This is the simplest choice but produces O(n²) on already-sorted input. For production code, replace int pivot = arr[hi] with a random or median-of-three selection.

The partition uses strict < comparison, which means equal elements end up to the right of the pivot. This causes some swapping inefficiency on inputs with many duplicates - the three-way partition scheme handles this better but is more complex.

The algorithm sorts in place. The only extra memory is the recursion stack, which is O(log n) on balanced partitions or O(n) on degenerate ones.

Example Walkthrough

Let us trace Quick Sort on [5, 2, 8, 1, 9, 3]. We will pick the last element as pivot each time.

Call 1: quickSort(arr, 0, 5)

Pivot is arr[5] = 3. Partition [5, 2, 8, 1, 9, 3]:

Start: arr=[5, 2, 8, 1, 9, 3], lo=0, hi=5, pivot=3, i=-1

j=0: arr[0]=5 < 3? No, skip.
j=1: arr[1]=2 < 3? Yes. i=0, swap arr[0] with arr[1]:
     [2, 5, 8, 1, 9, 3]
j=2: arr[2]=8 < 3? No, skip.
j=3: arr[3]=1 < 3? Yes. i=1, swap arr[1] with arr[3]:
     [2, 1, 8, 5, 9, 3]
j=4: arr[4]=9 < 3? No, skip.

End of loop. Swap arr[i+1]=arr[2] with arr[hi]=arr[5]:
[2, 1, 3, 5, 9, 8]

Pivot 3 is now at index 2. Return 2.

After this partition, the array is [2, 1, 3, 5, 9, 8]. Everything to the left of index 2 ([2, 1]) is less than 3. Everything to the right ([5, 9, 8]) is greater. The pivot 3 is in its final position.

Now recurse on arr[0..1] and arr[3..5].

Call 2: quickSort(arr, 0, 1)

Pivot is arr[1] = 1. Partition [2, 1]:

Start: arr=[2, 1, 3, 5, 9, 8], lo=0, hi=1, pivot=1, i=-1

j=0: arr[0]=2 < 1? No, skip.

End of loop. Swap arr[i+1]=arr[0] with arr[hi]=arr[1]:
[1, 2, 3, 5, 9, 8]

Pivot 1 is now at index 0. Return 0.

Recurse on arr[0..-1] (empty, base case) and arr[1..1] (single element, base case). Left side is done.

Call 3: quickSort(arr, 3, 5)

Pivot is arr[5] = 8. Partition [5, 9, 8]:

Start: arr=[1, 2, 3, 5, 9, 8], lo=3, hi=5, pivot=8, i=2

j=3: arr[3]=5 < 8? Yes. i=3, swap arr[3] with arr[3] (no change):
     [1, 2, 3, 5, 9, 8]
j=4: arr[4]=9 < 8? No, skip.

End of loop. Swap arr[i+1]=arr[4] with arr[hi]=arr[5]:
[1, 2, 3, 5, 8, 9]

Pivot 8 is now at index 4. Return 4.

Recurse on arr[3..3] (base case) and arr[5..5] (base case). Right side is done.

Final sorted array: [1, 2, 3, 5, 8, 9]

The recursion tree was reasonably balanced - three partition calls did the work. On adversarial input (already sorted with last-element pivot), the tree would degenerate into a linear chain of n calls, producing O(n²) behavior.

graph TD
    A["[5, 2, 8, 1, 9, 3]<br/>pivot=3"] --> B["[2, 1]<br/>pivot=1"]
    A --> C["[5, 9, 8]<br/>pivot=8"]
    B --> D["[]<br/>base"]
    B --> E["[2]<br/>base"]
    C --> F["[5]<br/>base"]
    C --> G["[9]<br/>base"]
    
    style A fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9

This diagram shows the recursion tree for Quick Sort on our example. The top node is the initial partition with pivot three. The left subtree is the partition of two and one with pivot one. The right subtree is the partition of five, nine, and eight with pivot eight. The leaves are single-element or empty segments which are base cases. The tree is reasonably balanced for this input, giving O of n log n behavior.

Complexity Analysis

Stability: Quick Sort is not stable. The partition swaps elements freely, which can reorder equal elements.

Why the Average Case Is O(n log n)

The recurrence for a balanced partition is T(n) = 2T(n/2) + O(n), which is O(n log n) by the Master Theorem.

For random input with random pivot selection, partitions are balanced on average. The probability of a maximally unbalanced split at every level is astronomically low. In practice, Quick Sort with random pivots is consistently O(n log n).

Why the Worst Case Is O(n²)

If the pivot is always the smallest or largest element, the partition splits into 0 elements and n-1 elements. The recurrence becomes T(n) = T(n - 1) + O(n), which is O(n²).

This happens most easily with a naive pivot strategy. For example, "always pick the last element" produces O(n²) on already-sorted input - because the last element is always the maximum.

This worst case is why production code uses random or median-of-three pivots. With random pivots, the worst case still exists in theory but is so unlikely it does not matter in practice.

Why It Is Not Stable

The partition step swaps elements based on their relationship to the pivot. Equal elements can be swapped past each other, breaking their original order. There are stable variants of Quick Sort, but they require extra memory and are slower - usually not worth it.

If you need stability, use Merge Sort instead.

Why It Is Often Fast in Practice

Quick Sort has the same average complexity as Merge Sort, but it is usually faster in wall-clock time. A few reasons:

• In-place. No allocation overhead, no copying to a temp buffer.
• Good cache behavior. Partitioning accesses memory in a tight, sequential pattern.
• Low constant factors. The inner loop is simple and tight.

These advantages compound. Quick Sort is often 2-3x faster than Merge Sort on real hardware despite having the same Big O.

When to Use Quick Sort

Good Fit

• General-purpose sorting where speed matters and worst case is acceptable. This is most production sorting code. Quick Sort with randomized pivots is the default.
• In-place sorting with limited memory. Quick Sort uses O(log n) recursion stack space. Merge Sort uses O(n) heap memory. For memory-constrained environments, Quick Sort wins.
• Sorting arrays (not linked lists). Quick Sort excels at array sorting due to cache behavior. Linked lists do not benefit.

Not Ideal For

• When worst-case predictability matters. Real-time systems or adversarial environments should prefer Merge Sort, Heap Sort, or Introsort (which falls back to Heap Sort).
• When stability is required. Use Merge Sort.
• Linked lists. Merge Sort handles linked lists more naturally because it does not need random access.

Why Most Standard Libraries Use Quick Sort (with Adaptations)

Most language standard libraries use Quick Sort variants for primitive arrays:

• Java's Arrays.sort(int[]) uses dual-pivot Quick Sort.
• C++'s std::sort uses Introsort - Quick Sort with a Heap Sort fallback to guarantee O(n log n).
• Go's sort.Sort uses introsort-like Quick Sort.

The reason: Quick Sort's average-case speed is hard to beat, and the worst case can be engineered away with smart pivot selection and fallback strategies.

For object arrays where stability matters, libraries switch to Merge Sort variants like TimSort.

Quick Sort vs Merge Sort

The two big O(n log n) sorts. Their trade-offs:

Quick Sort wins on space and average speed. Merge Sort wins on stability and worst-case guarantees. The right choice depends on what you care about.

The next chapter covers Heap Sort, the third major O(n log n) algorithm - with yet another set of trade-offs.

Back to DSA Mastery - Interview Prep, End to End