Quick Sort is one of the most widely used sorting algorithms. It follows a divide-and-conquer approach, but instead of splitting the array evenly, it selects a pivot and partitions the array into elements smaller and larger than the pivot.

When implemented well, Quick Sort achieves an average time complexity of O(n log n) and is fast in practice due to good cache locality. Its performance depends on pivot selection: poor choices can lead to O(n^2) time in the worst case.

This chapter covers how Quick Sort works, how partitioning is performed, how to choose pivots effectively, and how to implement the algorithm.

Quick Sort is a divide-and-conquer sorting algorithm. Its core operation is partitioning:

After each partition, the pivot is in its final position and will never move again. Each recursive call places more pivots in their correct positions until the entire array is sorted.

The diagram above captures the entire algorithm: pick a pivot, partition, then recurse on each half.

Merge Sort does most of its work in the merge step that combines two sorted halves. Quick Sort does most of its work in the partition step. By the time the recursion reaches its base case (sub-arrays of size 0 or 1), the array is already sorted. There is nothing left to combine.

The algorithm has two main components: the partition operation and the recursive driver.

The Partition Operation

Partitioning is the heart of Quick Sort. There are two classic partition schemes:

Lomuto Partition Scheme (simpler, easier to understand):

Hoare Partition Scheme (more efficient):

The implementation below uses Lomuto because it is easier to follow and less error-prone to implement. Hoare's scheme performs fewer swaps but is trickier to implement correctly.

Step-by-Step Process

The full Quick Sort algorithm using Lomuto partition:

The recursion tree fans out like a binary tree. In the best case (balanced partitions), the tree has log n levels, and each level does O(n) work during partitioning. That gives us O(n log n) total.

The partition function does the real work: it places the pivot in its correct position and returns that index. The quickSort function handles the recursion.

Why O(n log n) on Average?

Each partition step does O(n) work, scanning through the sub-array once. The key question is: how many levels of recursion are there?

When the pivot splits the array roughly in half each time, the recursion depth is log n. Each level does a total of O(n) work across all partitions at that level. So the total work is O(n) * O(log n) = O(n log n).

Why O(n^2) in the Worst Case?

The worst case happens when the partition is maximally unbalanced. If the pivot is always the smallest or largest element, one partition gets n-1 elements and the other gets 0 elements. This creates n levels of recursion instead of log n, and each level still does O(n) work. The total becomes O(n) * O(n) = O(n^2).

When does this happen? The classic scenario: the array is already sorted (ascending or descending), and you always pick the first or last element as the pivot. Every partition produces the worst possible split.

Space Complexity

Quick Sort sorts in-place, so it does not allocate extra arrays. However, it uses the call stack for recursion. In the best case, the recursion depth is O(log n). In the worst case, it is O(n), which can cause a stack overflow on very large sorted arrays.

Stability

Quick Sort is not stable. The partition step swaps elements across long distances, and an equal element can be moved past another equal element that originally appeared before it.

For example, with the array [3a, 1, 3b, 2] and pivot 2 (Lomuto, last element), the partition first moves 1 to the front, then swaps the pivot 2 into position, producing [1, 2, 3b, 3a]. The original 3a, 3b order is reversed.

A stable variant is possible by partitioning into separate buffers and concatenating them, but this gives up the O(1) auxiliary-space property. Production implementations that need stability use merge sort or TimSort instead.

The left tree shows balanced partitions (best case), where the depth is log n. The right tree shows unbalanced partitions (worst case), where the depth is n. Pivot selection determines which shape the recursion takes.

Good Fit

Not Ideal For

Pivot Selection Strategies

Pivot selection has a large effect on performance. A poorly chosen pivot leads to O(n^2), while a well chosen one keeps the algorithm at O(n log n).

1. Last or First Element (Naive) Simple to implement, but it degrades to O(n^2) on sorted or nearly sorted data, which is a common input shape.

2. Random Pivot Pick a random element and swap it with the last element before partitioning. This makes the worst case very unlikely, though not impossible. The expected time complexity is O(n log n) regardless of input order.

3. Median-of-Three Pick the median of the first, middle, and last elements. This avoids the worst case on sorted data and performs well in practice. The C++ STL std::sort (introsort) uses median-of-three for pivot selection.

The table below summarizes the trade-offs: