Sorting Algorithm

Quick Sort

“The Standard Library Darling”

Time: O(n log n)

Space: O(log n)

History

Tony Hoare invented Quick Sort in 1959. He was a visiting student in Moscow trying to translate Russian to English, and he needed a faster way to sort words.

It is the rockstar of sorting. It's the default `.sort()` implementation in many languages (or a variant of it). It introduced the "Divide and Conquer" strategy to the mainstream.

How It Works

Quick Sort relies on a "Pivot." It picks one element and organizes the rest of the array around it: everything smaller goes to the left, everything larger goes to the right.

The Algorithm Step-by-Step

Pick Pivot: Select an element (middle, last, or random).
Partition: Reorder the array so the Pivot is in its final home. All smaller items are to its left; all larger items are to its right.
Recursion: Apply the same logic to the sub-list on the left and the sub-list on the right.
Base Case: If a list has 0 or 1 items, it is sorted.

The Pivot Problem

If you pick a bad pivot (like always picking the first item on a sorted list), Quick Sort breaks down. Modern implementations use "Median of Three" (checking start, middle, and end) to avoid this.

Best CaseO(n log n)

If the pivot cuts the list roughly in half every time, the recursion tree is perfectly balanced.

Worst CaseO(n²)

If the pivot is always the smallest or largest item, you essentially create a very expensive Bubble Sort.

Average CaseO(n log n)

On random data, it is blazing fast. It often outperforms Merge Sort because it works in-place and plays nice with CPU caches.

SpaceO(log n)

It consumes stack space for the recursion. It's not strictly O(1) space.

Code Walkthrough

Real implementations in multiple programming languages. Select a language to view idiomatic code.

1def quick_sort(arr: list[int], lo: int = 0, hi: int | None = None) -> None:
2    """Sort array in-place using quick sort (Lomuto partition)."""
3    if hi is None:
4        hi = len(arr) - 1
5
6    if lo < hi:
7        pivot_idx = partition(arr, lo, hi)
8        quick_sort(arr, lo, pivot_idx - 1)
9        quick_sort(arr, pivot_idx + 1, hi)
10
11def partition(arr: list[int], lo: int, hi: int) -> int:
12    """Lomuto partition scheme with last element as pivot."""
13    pivot = arr[hi]
14    i = lo - 1
15
16    for j in range(lo, hi):
17        if arr[j] <= pivot:
18            i += 1
19            arr[i], arr[j] = arr[j], arr[i]
20
21    arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
22    return i + 1