Quick Sort

Partition-based sorting that picks a pivot and recursively sorts subarrays in-place.

O(n log n)Sorting

Phase 1f(x)

The Mathematics

Partition-based sorting, recurrence analysis, and average-case complexity

Core Idea

Quick Sort selects a pivot element and partitions the array so that all elements $\leq$ pivot are on the left and all elements $>$ pivot are on the right. The pivot is then in its final sorted position.

\text{QuickSort}(A) : \text{partition around pivot, then recurse on both halves}

Recurrence Relation

If the pivot lands at position $k$ , we get two subproblems of sizes $k$ and $n - k - 1$ . Partitioning takes $O(n)$ :

T(n) = T(k) + T(n - k - 1) + O(n)

Worst case ( $k = 0$ every time, e.g., already sorted input):

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

Average case (pivot lands roughly in the middle):

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

Lomuto Partition Scheme

Choose the last element as pivot. Maintain index $i$ such that $A[lo..i{-}1] \leq \text{pivot}$ and $A[i..j{-}1] > \text{pivot}$ :

\text{for } j = lo \text{ to } hi{-}1: \text{if } A[j] \leq \text{pivot, swap } A[i] \leftrightarrow A[j],\; i{+}{+}

Finally, swap $A[i] \leftrightarrow A[hi]$ to place the pivot at index $i$ .

Why Quick Sort Is Fast in Practice

Despite $O(n^2)$ worst case, Quick Sort is often faster than Merge Sort due to: (1) in-place partitioning (no extra $O(n)$ memory), (2) cache-friendly sequential access, and (3) randomized pivot selection makes worst case extremely unlikely — expected $O(n \log n)$ with high probability.

Phase 2▶

See It Work

Sorting [6, 3, 8, 2, 5, 1] via pivot partitioning

T(n) = T(k) + T(n{-}k{-}1) + O(n)

Step 1 of 9

Start with unsorted array. Quick Sort picks a pivot and partitions elements around it.

Phase 3</>

The Code

Mapping partition logic to Python with Lomuto scheme

Mathematical Formulation

\text{if } lo < hi

Base case: subarrays of size ≤ 1 are already sorted

p = \text{partition}(A, lo, hi)

Partition returns the final index of the pivot

T(k) + T(n{-}k{-}1)

Two recursive calls on subarrays left and right of pivot

\text{pivot} = A[hi]

Lomuto partition: choose the last element as pivot

A[j] \leq \text{pivot} \Rightarrow \text{swap to left}

Move elements ≤ pivot to the left partition

A[i] \leftrightarrow A[hi] \Rightarrow \text{pivot in place}

Place pivot in its final sorted position

Python Implementation

def quick_sort(A, lo=0, hi=None):
    if hi is None: hi = len(A) - 1
    if lo < hi:
        p = partition(A, lo, hi)     # Partition
        quick_sort(A, lo, p - 1)     # Sort left
        quick_sort(A, p + 1, hi)     # Sort right

def partition(A, lo, hi):
    pivot = A[hi]                    # Choose last as pivot
    i = lo
    for j in range(lo, hi):         # Scan elements
        if A[j] <= pivot:
            A[i], A[j] = A[j], A[i] # Swap to left
            i += 1
    A[i], A[hi] = A[hi], A[i]       # Place pivot
    return i