Sorting

Quick Sort

TimeO(n log n) SpaceO(log n)

Imagine organizing a group photo by height. You pick one person as a reference. Everyone shorter stands left, everyone taller stands right. Then you repeat this in each group. Once every group is one person, everyone is in order — and nobody had to move far.

When to use it: General-purpose sorting when average-case performance matters and O(n) extra space is undesirable. Quick sort is typically faster in practice than merge sort due to cache friendliness.

Key insight: Partitioning is O(n) and puts the pivot in its final position. With a good pivot, each recursion halves the problem, giving O(n log n) average.

Common trap: Picking the first or last element as pivot on already-sorted data gives O(n^2). Use randomized pivot selection or median-of-three to avoid this.

function quickSort(arr, low, high):
    if low < high:
        pivotIndex = partition(arr, low, high)
        quickSort(arr, low, pivotIndex - 1)     # sort left of pivot
        quickSort(arr, pivotIndex + 1, high)     # sort right of pivot

function partition(arr, low, high):
    pivot = arr[high]                            # choose last element as pivot
    i = low - 1                                  # boundary of "less than pivot"

    for j = low to high - 1:
        if arr[j] <= pivot:
            i = i + 1
            swap(arr[i], arr[j])                 # move small element to left side

    swap(arr[i + 1], arr[high])                  # place pivot in correct position
    return i + 1

import random


def quick_sort(arr: list[int]) -> list[int]:
    """Out-of-place quick sort for clarity."""
    if len(arr) <= 1:
        return arr

    pivot = arr[random.randint(0, len(arr) - 1)]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    return quick_sort(left) + middle + quick_sort(right)


def quick_sort_inplace(arr: list[int], low: int = 0, high: int | None = None) -> None:
    """In-place quick sort with Lomuto partition."""
    if high is None:
        high = len(arr) - 1

    if low < high:
        pivot_idx = partition(arr, low, high)
        quick_sort_inplace(arr, low, pivot_idx - 1)
        quick_sort_inplace(arr, pivot_idx + 1, high)


def partition(arr: list[int], low: int, high: int) -> int:
    # Randomized pivot to avoid worst-case on sorted input
    rand_idx = random.randint(low, high)
    arr[rand_idx], arr[high] = arr[high], arr[rand_idx]

    pivot = arr[high]
    i = low - 1

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

Problem: Find the k-th smallest element in an unsorted array in better than O(n log n) average time.

How would you approach this?

Answer: This is Quickselect, a variant of quick sort's partition. Partition once, then recurse only into the side containing the k-th element. Average case: O(n) because you halve the problem each time without sorting the other half.

Problem: Sort a large array of integers in-place with the fastest average-case performance.

How would you approach this?

Answer: This is quick sort with randomized pivot. It sorts in-place using O(log n) stack space, and its cache-friendly access pattern makes it faster in practice than merge sort for arrays.

Time: O(n log n) average, O(n^2) worst case. The average case assumes the pivot roughly halves the array, giving log n levels of O(n) partitioning. The worst case occurs when the pivot is always the min or max, creating n levels. Randomized pivot makes the worst case extremely unlikely.

Space: O(log n) average for the recursion stack. In the worst case (unbalanced partitions), the stack depth is O(n). Tail-call optimization on the larger partition can guarantee O(log n) stack space.