Quick Sort — The Fastest Practical Sorting Algorithm with Complete Analysis

Master quick sort completely — partition schemes (Lomuto and Hoare), randomized quick sort, 3-way partition for duplicates, average-case proof, worst-case prevention, why quick sort beats merge sort in practice despite equal asymptotic complexity, and tail-call optimization.

The Core Idea

Quick sort partitions the array around a pivot element so that:

All elements smaller than pivot go to its left
All elements larger than pivot go to its right
The pivot is now in its final sorted position

Then recursively sort the left and right partitions.

Example

[3, 6, 8, 10, 1, 2, 1] pivot = 1 (last element) After partition: [1, 1, | 8, 10, 6, 2, 3] → pivot 1 is at its final position ↑↑ All ≤1 All >1 Recursively sort left [1] and right [8,10,6,2,3]

Randomized Quick Sort

The problem: Worst case O(n²) occurs when pivot always picks the smallest or largest element — e.g., sorted array with last-element pivot.

The fix: Choose a random pivot before partitioning.

Example

import random def randomized_quicksort(arr, low=None, high=None): """ Random pivot selection eliminates worst-case patterns. Expected O(n log n) regardless of input. """ if low is None: low, high = 0, len(arr) - 1 if low < high: # Randomly pick pivot and swap with last element rand_idx = random.randint(low, high) arr[rand_idx], arr[high] = arr[high], arr[rand_idx] pi = lomuto_partition(arr, low, high) randomized_quicksort(arr, low, pi - 1) randomized_quicksort(arr, pi + 1, high) return arr

Why randomization works:

Any specific "bad" input is only bad for one particular pivot sequence
With random pivots, the probability that every pivot is adversarial is (1/n)ⁿ — essentially zero
Expected number of comparisons: 2n ln(n) ≈ 1.39 n log₂n

3-Way Partition — Handles Duplicates Efficiently

When the array has many duplicate elements, standard Quick Sort degrades. The Dutch National Flag 3-way partition handles this:

Example

def quicksort_3way(arr, low=None, high=None): """ 3-way partition: split into <pivot, ==pivot, >pivot. O(n) for arrays with all identical elements. Best for arrays with many duplicates. """ if low is None: low, high = 0, len(arr) - 1 if low >= high: return arr pivot = arr[low + random.randint(0, high - low)] # Dutch National Flag partition lt = low # arr[low..lt-1] < pivot gt = high # arr[gt+1..high] > pivot i = low # arr[lt..i-1] == pivot while i <= gt: if arr[i] < pivot: arr[lt], arr[i] = arr[i], arr[lt] lt += 1; i += 1 elif arr[i] > pivot: arr[gt], arr[i] = arr[i], arr[gt] gt -= 1 else: i += 1 quicksort_3way(arr, low, lt - 1) # Sort < portion quicksort_3way(arr, gt + 1, high) # Sort > portion # Middle (== pivot) is already sorted return arr print(quicksort_3way([3, 3, 3, 1, 3, 2, 3])) # [1, 2, 3, 3, 3, 3, 3]

Complexity Analysis

Best Case — Ω(n log n): Perfectly Balanced Pivots

Example

Each partition splits array exactly in half: T(n) = 2T(n/2) + O(n) → O(n log n)

Average Case — Θ(n log n): Random Input

The expected number of comparisons when each permutation is equally likely:

Example

C(n) = (n+1) + 2/n × Σ C(k) for k=0 to n-1 Solving: C(n) = 2(n+1)H(n) - 2n ≈ 2n ln(n) ≈ 1.39 n log₂n

Quick Sort does about 39% more comparisons than Merge Sort on average, but is faster in practice due to better cache behavior.

Worst Case — O(n²): Always Bad Pivot

Partition [1,2,3,4,5]	pivot=5, left=[1,2,3,4], right=[]
Partition [1,2,3,4]	pivot=4, left=[1,2,3], right=[]
T(n) = T(n-1) + O(n)	O(n²)

Prevention:

Random pivot selection
Median-of-three pivot (choose median of first, middle, last)
3-way partition for duplicate-heavy inputs

Why Quick Sort Beats Merge Sort in Practice

Despite equal Θ(n log n) average complexity, Quick Sort is faster in practice:

1. Cache Friendliness

Merge Sort: creates new arrays	random memory access → cache misses
Quick Sort: in-place swaps	sequential memory access → cache hits
Cache miss penalty	~100x slower than cache hit
For modern processors	Quick Sort is 2-4x faster in practice

2. Memory Allocation

Example

Merge Sort: allocates O(n) auxiliary memory → malloc/free overhead Quick Sort: O(1) auxiliary memory → no allocation needed

3. Better Constant Factors

Quick Sort's inner loop

while arr[i] < pivot: i++ ← one comparison, no extra work

Merge Sort's inner loop

if arr[i] <= arr[j]: ← comparison

result.append(arr[i]) ← copy to new array (expensive)

i++

4. Recursion Depth

Merge Sort	always log n levels
Quick Sort (average)	log n levels, but much smaller constant
Quick Sort (worst): n levels	tail-call optimization helps

Tail-Call Optimization for Quick Sort

python example

def quicksort_tco(arr, low, high):
    """
    Tail-call optimized: always recurse into the smaller partition first.
    Guarantees O(log n) stack depth regardless of pivot quality.
    """
    while low < high:
        pi = lomuto_partition(arr, low, high)

        if pi - low < high - pi:
            # Left partition is smaller → recurse left, loop right
            quicksort_tco(arr, low, pi - 1)
            low = pi + 1
        else:
            # Right partition is smaller → recurse right, loop left
            quicksort_tco(arr, pi + 1, high)
            high = pi - 1

By always recursing into the smaller partition and using a loop for the larger, the maximum recursion depth is O(log n) even in the worst case.

Summary

Property	Quicksort
Best case	O(n log n)
Average case	O(n log n) — ~1.39n log n comparisons
Worst case	O(n²) — prevented with random pivot
Space	O(log n) avg, O(n) worst (with TCO: O(log n) always)
Stable	❌ No
Adaptive	❌ No (without 3-way partition)
Cache friendly	✅ Yes — in-place access

Choose Quick Sort when:

Average performance matters most
Memory is limited (O(log n) space)
Data is random or uniformly distributed
Used with randomization (eliminates adversarial inputs)

Choose Merge Sort instead when:

Stability is required
Guaranteed O(n log n) worst case needed
Sorting linked lists

*Next Lesson: Heap Sort*

The Core Idea

Quick sort partitions the array around a pivot element so that:

All elements smaller than pivot go to its left
All elements larger than pivot go to its right
The pivot is now in its final sorted position

Then recursively sort the left and right partitions.

Example

[3, 6, 8, 10, 1, 2, 1] pivot = 1 (last element) After partition: [1, 1, | 8, 10, 6, 2, 3] → pivot 1 is at its final position ↑↑ All ≤1 All >1 Recursively sort left [1] and right [8,10,6,2,3]

Randomized Quick Sort

The problem: Worst case O(n²) occurs when pivot always picks the smallest or largest element — e.g., sorted array with last-element pivot.

The fix: Choose a random pivot before partitioning.

Example

Why randomization works:

Any specific "bad" input is only bad for one particular pivot sequence
With random pivots, the probability that every pivot is adversarial is (1/n)ⁿ — essentially zero
Expected number of comparisons: 2n ln(n) ≈ 1.39 n log₂n

3-Way Partition — Handles Duplicates Efficiently

When the array has many duplicate elements, standard Quick Sort degrades. The Dutch National Flag 3-way partition handles this:

Example

Complexity Analysis

Best Case — Ω(n log n): Perfectly Balanced Pivots

Example

Each partition splits array exactly in half: T(n) = 2T(n/2) + O(n) → O(n log n)

Average Case — Θ(n log n): Random Input

The expected number of comparisons when each permutation is equally likely:

Example

C(n) = (n+1) + 2/n × Σ C(k) for k=0 to n-1 Solving: C(n) = 2(n+1)H(n) - 2n ≈ 2n ln(n) ≈ 1.39 n log₂n

Quick Sort does about 39% more comparisons than Merge Sort on average, but is faster in practice due to better cache behavior.

Worst Case — O(n²): Always Bad Pivot

Partition [1,2,3,4,5]	pivot=5, left=[1,2,3,4], right=[]
Partition [1,2,3,4]	pivot=4, left=[1,2,3], right=[]
T(n) = T(n-1) + O(n)	O(n²)

Prevention:

Random pivot selection
Median-of-three pivot (choose median of first, middle, last)
3-way partition for duplicate-heavy inputs

Why Quick Sort Beats Merge Sort in Practice

Despite equal Θ(n log n) average complexity, Quick Sort is faster in practice:

1. Cache Friendliness

Merge Sort: creates new arrays	random memory access → cache misses
Quick Sort: in-place swaps	sequential memory access → cache hits
Cache miss penalty	~100x slower than cache hit
For modern processors	Quick Sort is 2-4x faster in practice

2. Memory Allocation

Example

Merge Sort: allocates O(n) auxiliary memory → malloc/free overhead Quick Sort: O(1) auxiliary memory → no allocation needed

3. Better Constant Factors

Quick Sort's inner loop

while arr[i] < pivot: i++ ← one comparison, no extra work

Merge Sort's inner loop

if arr[i] <= arr[j]: ← comparison

result.append(arr[i]) ← copy to new array (expensive)

i++

4. Recursion Depth

Merge Sort	always log n levels
Quick Sort (average)	log n levels, but much smaller constant
Quick Sort (worst): n levels	tail-call optimization helps

Tail-Call Optimization for Quick Sort

python example

def quicksort_tco(arr, low, high):
    """
    Tail-call optimized: always recurse into the smaller partition first.
    Guarantees O(log n) stack depth regardless of pivot quality.
    """
    while low < high:
        pi = lomuto_partition(arr, low, high)

        if pi - low < high - pi:
            # Left partition is smaller → recurse left, loop right
            quicksort_tco(arr, low, pi - 1)
            low = pi + 1
        else:
            # Right partition is smaller → recurse right, loop left
            quicksort_tco(arr, pi + 1, high)
            high = pi - 1

By always recursing into the smaller partition and using a loop for the larger, the maximum recursion depth is O(log n) even in the worst case.

Summary

Property	Quicksort
Best case	O(n log n)
Average case	O(n log n) — ~1.39n log n comparisons
Worst case	O(n²) — prevented with random pivot
Space	O(log n) avg, O(n) worst (with TCO: O(log n) always)
Stable	❌ No
Adaptive	❌ No (without 3-way partition)
Cache friendly	✅ Yes — in-place access

Choose Quick Sort when:

Average performance matters most
Memory is limited (O(log n) space)
Data is random or uniformly distributed
Used with randomization (eliminates adversarial inputs)

Choose Merge Sort instead when:

Stability is required
Guaranteed O(n log n) worst case needed
Sorting linked lists

*Next Lesson: Heap Sort*

Quick Sort — The Fastest Practical Sorting Algorithm with Complete Analysis

The Core Idea

Randomized Quick Sort

3-Way Partition — Handles Duplicates Efficiently

Complexity Analysis

Best Case — Ω(n log n): Perfectly Balanced Pivots

Average Case — Θ(n log n): Random Input

Worst Case — O(n²): Always Bad Pivot

Why Quick Sort Beats Merge Sort in Practice

1. Cache Friendliness

2. Memory Allocation

3. Better Constant Factors

Quick Sort's inner loop

Merge Sort's inner loop

4. Recursion Depth

Tail-Call Optimization for Quick Sort

Summary

Continue learning this concept

Quick Sort — The Fastest Practical Sorting Algorithm with Complete Analysis

The Core Idea

Randomized Quick Sort

3-Way Partition — Handles Duplicates Efficiently

Complexity Analysis

Best Case — Ω(n log n): Perfectly Balanced Pivots

Average Case — Θ(n log n): Random Input

Worst Case — O(n²): Always Bad Pivot

Why Quick Sort Beats Merge Sort in Practice

1. Cache Friendliness

2. Memory Allocation

3. Better Constant Factors

Quick Sort's inner loop

Merge Sort's inner loop

4. Recursion Depth

Tail-Call Optimization for Quick Sort

Summary

Continue learning this concept