Quick Sort

Dec 13, 2025 · 10 min read · quick-sort sorting divide-and-conquer algorithms ·

Share on:

Quick sort is an efficient, in-place, comparison-based sorting algorithm that uses divide-and-conquer. It has $O(n \log n)$ average time complexity but $O(n^2)$ worst case.

Algorithm Overview

Divide and Conquer Strategy

Partition: Choose a pivot and partition array so that:
- Elements ≤ pivot are on the left
- Elements > pivot are on the right
Conquer: Recursively sort left and right partitions
Combine: No work needed (in-place sorting)

Mathematical Formulation

$$ \text{QuickSort}(A, \text{low}, \text{high}) = \begin{cases} A & \text{if low} \geq \text{high} \\ \text{QuickSort}(A, \text{low}, p-1) \cup {A[p]} \cup \text{QuickSort}(A, p+1, \text{high}) & \text{otherwise} \end{cases} $$

where $p = \text{Partition}(A, \text{low}, \text{high})$ is the pivot's final position.

Visualization

Partition Schemes

1. Lomuto Partition Scheme

Simpler but less efficient

 1// LomutoPartition uses last element as pivot
 2func LomutoPartition(arr []int, low, high int) int {
 3    pivot := arr[high] // Choose last element as pivot
 4    i := low - 1       // Index of smaller element
 5    
 6    for j := low; j < high; j++ {
 7        if arr[j] <= pivot {
 8            i++
 9            arr[i], arr[j] = arr[j], arr[i]
10        }
11    }
12    
13    // Place pivot in correct position
14    arr[i+1], arr[high] = arr[high], arr[i+1]
15    return i + 1
16}
17
18func QuickSortLomuto(arr []int, low, high int) {
19    if low < high {
20        pi := LomutoPartition(arr, low, high)
21        
22        QuickSortLomuto(arr, low, pi-1)  // Before pivot
23        QuickSortLomuto(arr, pi+1, high) // After pivot
24    }
25}
26
27// Example
28func main() {
29    arr := []int{10, 7, 8, 9, 1, 5}
30    QuickSortLomuto(arr, 0, len(arr)-1)
31    fmt.Println(arr) // [1, 5, 7, 8, 9, 10]
32}

Invariant:

$A[\text{low} \ldots i] \leq \text{pivot}$
$A[i+1 \ldots j-1] > \text{pivot}$
$A[j \ldots \text{high}-1]$ not yet processed

Time: $O(n)$

2. Hoare Partition Scheme

Original and more efficient

 1// HoarePartition uses two pointers from both ends
 2func HoarePartition(arr []int, low, high int) int {
 3    pivot := arr[low] // Choose first element as pivot
 4    i, j := low-1, high+1
 5    
 6    for {
 7        // Move i right while arr[i] < pivot
 8        for {
 9            i++
10            if arr[i] >= pivot {
11                break
12            }
13        }
14        
15        // Move j left while arr[j] > pivot
16        for {
17            j--
18            if arr[j] <= pivot {
19                break
20            }
21        }
22        
23        if i >= j {
24            return j
25        }
26        
27        arr[i], arr[j] = arr[j], arr[i]
28    }
29}
30
31func QuickSortHoare(arr []int, low, high int) {
32    if low < high {
33        pi := HoarePartition(arr, low, high)
34        
35        QuickSortHoare(arr, low, pi)    // Left partition
36        QuickSortHoare(arr, pi+1, high) // Right partition
37    }
38}

Swaps: About 3 times fewer than Lomuto

Time: $O(n)$

3. Three-Way Partition (Dutch National Flag)

For arrays with many duplicates

 1// ThreeWayPartition partitions into <, =, > pivot
 2func ThreeWayPartition(arr []int, low, high int) (int, int) {
 3    if high - low <= 1 {
 4        if arr[low] > arr[high] {
 5            arr[low], arr[high] = arr[high], arr[low]
 6        }
 7        return low, high
 8    }
 9    
10    pivot := arr[low]
11    lt, i, gt := low, low+1, high
12    
13    for i <= gt {
14        if arr[i] < pivot {
15            arr[lt], arr[i] = arr[i], arr[lt]
16            lt++
17            i++
18        } else if arr[i] > pivot {
19            arr[i], arr[gt] = arr[gt], arr[i]
20            gt--
21        } else {
22            i++
23        }
24    }
25    
26    return lt, gt
27}
28
29func QuickSort3Way(arr []int, low, high int) {
30    if low >= high {
31        return
32    }
33    
34    lt, gt := ThreeWayPartition(arr, low, high)
35    
36    QuickSort3Way(arr, low, lt-1)  // Less than pivot
37    QuickSort3Way(arr, gt+1, high) // Greater than pivot
38    // Elements from lt to gt are equal to pivot
39}
40
41// Example
42func main() {
43    arr := []int{4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4}
44    QuickSort3Way(arr, 0, len(arr)-1)
45    fmt.Println(arr) // [1, 1, 4, 4, 4, 4, 4, 4, 4, 9, 9, 9]
46}

Advantage: Linear time for arrays with many duplicates

Time: $O(n)$ when all elements are equal

Complexity Analysis

Time Complexity

Best case: $O(n \log n)$

Pivot divides array into two equal halves

Recurrence: $$ T(n) = 2T(n/2) + O(n) $$

Solution: $T(n) = O(n \log n)$

Average case: $O(n \log n)$

Expected partition is reasonably balanced

Analysis: Even if partition is 1:9, still $O(n \log n)$: $$ T(n) = T(n/10) + T(9n/10) + O(n) = O(n \log n) $$

Worst case: $O(n^2)$

Pivot is always smallest or largest element
Happens when array is already sorted (with naive pivot selection)

Recurrence: $$ T(n) = T(n-1) + O(n) = O(n^2) $$

Space Complexity

Best/Average case: $O(\log n)$

Recursion depth for balanced partitions

Worst case: $O(n)$

Recursion depth for unbalanced partitions

Optimization: Recurse on smaller partition first, iterate on larger

Guarantees $O(\log n)$ space even in worst case

Pivot Selection Strategies

1. Random Element

 1import "math/rand"
 2
 3func RandomizedPartition(arr []int, low, high int) int {
 4    // Choose random pivot
 5    randomIdx := low + rand.Intn(high-low+1)
 6    arr[randomIdx], arr[high] = arr[high], arr[randomIdx]
 7    
 8    return LomutoPartition(arr, low, high)
 9}
10
11func RandomizedQuickSort(arr []int, low, high int) {
12    if low < high {
13        pi := RandomizedPartition(arr, low, high)
14        RandomizedQuickSort(arr, low, pi-1)
15        RandomizedQuickSort(arr, pi+1, high)
16    }
17}

Pros: Expected $O(n \log n)$ regardless of input
Cons: Requires random number generation

2. Median-of-Three

 1func MedianOfThree(arr []int, low, high int) int {
 2    mid := low + (high-low)/2
 3    
 4    // Sort low, mid, high
 5    if arr[mid] < arr[low] {
 6        arr[low], arr[mid] = arr[mid], arr[low]
 7    }
 8    if arr[high] < arr[low] {
 9        arr[low], arr[high] = arr[high], arr[low]
10    }
11    if arr[mid] < arr[high] {
12        arr[mid], arr[high] = arr[high], arr[mid]
13    }
14    
15    // Place median at high-1
16    arr[mid], arr[high-1] = arr[high-1], arr[mid]
17    return high - 1
18}
19
20func QuickSortMedian3(arr []int, low, high int) {
21    if high - low < 3 {
22        // Use insertion sort for small arrays
23        insertionSort(arr, low, high)
24        return
25    }
26    
27    pivotIdx := MedianOfThree(arr, low, high)
28    arr[pivotIdx], arr[high] = arr[high], arr[pivotIdx]
29    
30    pi := LomutoPartition(arr, low, high)
31    QuickSortMedian3(arr, low, pi-1)
32    QuickSortMedian3(arr, pi+1, high)
33}

Pros:

Better pivot selection
Avoids worst case on sorted arrays
No randomness needed

Improvement: Reduces probability of worst case significantly

Optimizations

1. Tail Call Elimination

 1func QuickSortOptimized(arr []int, low, high int) {
 2    for low < high {
 3        pi := LomutoPartition(arr, low, high)
 4        
 5        // Recurse on smaller partition, iterate on larger
 6        if pi - low < high - pi {
 7            QuickSortOptimized(arr, low, pi-1)
 8            low = pi + 1
 9        } else {
10            QuickSortOptimized(arr, pi+1, high)
11            high = pi - 1
12        }
13    }
14}

Benefit: Guarantees $O(\log n)$ stack space even in worst case

2. Insertion Sort for Small Subarrays

 1const THRESHOLD = 10
 2
 3func QuickSortHybrid(arr []int, low, high int) {
 4    if high - low < THRESHOLD {
 5        insertionSort(arr, low, high)
 6        return
 7    }
 8    
 9    pi := LomutoPartition(arr, low, high)
10    QuickSortHybrid(arr, low, pi-1)
11    QuickSortHybrid(arr, pi+1, high)
12}
13
14func insertionSort(arr []int, low, high int) {
15    for i := low + 1; i <= high; i++ {
16        key := arr[i]
17        j := i - 1
18        for j >= low && arr[j] > key {
19            arr[j+1] = arr[j]
20            j--
21        }
22        arr[j+1] = key
23    }
24}

Improvement: 20-25% faster in practice

Complete Optimized Implementation

 1package main
 2
 3import (
 4    "fmt"
 5    "math/rand"
 6)
 7
 8const (
 9    THRESHOLD = 10
10    USE_MEDIAN_OF_THREE = true
11)
12
13func QuickSort(arr []int) {
14    quickSortHelper(arr, 0, len(arr)-1)
15}
16
17func quickSortHelper(arr []int, low, high int) {
18    for low < high {
19        // Use insertion sort for small subarrays
20        if high - low < THRESHOLD {
21            insertionSort(arr, low, high)
22            return
23        }
24        
25        // Partition
26        var pi int
27        if USE_MEDIAN_OF_THREE {
28            pi = partitionMedian3(arr, low, high)
29        } else {
30            pi = partitionLomuto(arr, low, high)
31        }
32        
33        // Tail call optimization: recurse on smaller, iterate on larger
34        if pi - low < high - pi {
35            quickSortHelper(arr, low, pi-1)
36            low = pi + 1
37        } else {
38            quickSortHelper(arr, pi+1, high)
39            high = pi - 1
40        }
41    }
42}
43
44func partitionLomuto(arr []int, low, high int) int {
45    pivot := arr[high]
46    i := low - 1
47    
48    for j := low; j < high; j++ {
49        if arr[j] <= pivot {
50            i++
51            arr[i], arr[j] = arr[j], arr[i]
52        }
53    }
54    
55    arr[i+1], arr[high] = arr[high], arr[i+1]
56    return i + 1
57}
58
59func partitionMedian3(arr []int, low, high int) int {
60    mid := low + (high-low)/2
61    
62    // Sort low, mid, high
63    if arr[mid] < arr[low] {
64        arr[low], arr[mid] = arr[mid], arr[low]
65    }
66    if arr[high] < arr[low] {
67        arr[low], arr[high] = arr[high], arr[low]
68    }
69    if arr[high] < arr[mid] {
70        arr[mid], arr[high] = arr[high], arr[mid]
71    }
72    
73    // Use mid as pivot
74    arr[mid], arr[high] = arr[high], arr[mid]
75    return partitionLomuto(arr, low, high)
76}
77
78func insertionSort(arr []int, low, high int) {
79    for i := low + 1; i <= high; i++ {
80        key := arr[i]
81        j := i - 1
82        for j >= low && arr[j] > key {
83            arr[j+1] = arr[j]
84            j--
85        }
86        arr[j+1] = key
87    }
88}
89
90func main() {
91    arr := []int{10, 7, 8, 9, 1, 5, 3, 6, 4, 2}
92    fmt.Println("Before:", arr)
93    QuickSort(arr)
94    fmt.Println("After:", arr)
95}

Comparison with Other Sorting Algorithms

Algorithm	Time (Best)	Time (Avg)	Time (Worst)	Space	Stable	In-Place
Quick Sort	$O(n \log n)$	$O(n \log n)$	$O(n^2)$	$O(\log n)$	No	Yes
Merge Sort	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	Yes	No
Heap Sort	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(1)$	No	Yes
Insertion Sort	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	Yes	Yes

Why Quick Sort is Fast in Practice

Despite $O(n^2)$ worst case, quick sort is often faster than merge sort and heap sort:

1. Cache Efficiency

In-place: Better cache locality, fewer cache misses

Sequential access: Partition scans array sequentially

2. Fewer Comparisons

Average: $1.39n \log n$ comparisons vs. $n \log n$ for merge sort

Constant factors: Lower overhead per operation

3. Fewer Swaps

Hoare partition: About $n/6$ swaps on average

Merge sort: $O(n \log n)$ moves

4. In-Place

No auxiliary array: Saves memory allocation/deallocation overhead

When to Use Quick Sort

✅ Use when:

Average case performance is critical
Memory is limited (in-place sorting)
Cache efficiency matters
Stability is not required
General-purpose sorting

❌ Don't use when:

Worst-case guarantee is needed (use merge sort or heap sort)
Stability is required (use merge sort or tim sort)
Data is nearly sorted (use insertion sort or tim sort)
Many duplicate elements without three-way partition

Common Interview Problems

1. Kth Largest Element

Problem: Find k-th largest element in unsorted array.

 1func FindKthLargest(nums []int, k int) int {
 2    return quickSelect(nums, 0, len(nums)-1, len(nums)-k)
 3}
 4
 5func quickSelect(nums []int, low, high, k int) int {
 6    if low == high {
 7        return nums[low]
 8    }
 9    
10    pi := LomutoPartition(nums, low, high)
11    
12    if k == pi {
13        return nums[k]
14    } else if k < pi {
15        return quickSelect(nums, low, pi-1, k)
16    } else {
17        return quickSelect(nums, pi+1, high, k)
18    }
19}

Time: $O(n)$ average, $O(n^2)$ worst

2. Sort Colors (Dutch National Flag)

Problem: Sort array with 3 distinct values.

Solution: Three-way partition.

Time: $O(n)$, one pass

Applications

General Purpose Sorting: Most language standard libraries
Selection Algorithm: Find k-th smallest element
Duplicate Detection: Three-way partition efficiently handles duplicates
Parallel Sorting: Partitioning can be parallelized effectively

Related Snippets

Binary Search
Binary search is an efficient algorithm for finding a target value in a sorted …
Binary Tree
A binary tree is a tree data structure where each node has at most two children, …
General Tree
A tree is a hierarchical data structure consisting of nodes connected by edges, …
Heap Data Structure
A heap is a specialized tree-based data structure that satisfies the heap …
Heap Sort
Heap sort is a comparison-based sorting algorithm that uses a binary heap data …
Linked List Operations
Optimal techniques for common linked list operations using pointer manipulation, …
LRU and LFU Cache
Cache replacement policies determine which items to evict when the cache is …
Merge Sort
Merge sort is a stable, comparison-based sorting algorithm that uses the …
Quadtree
A Quadtree is a tree data structure where each internal node has exactly four …
String Similarity Algorithms
Algorithms for measuring similarity between strings, used in spell checking, DNA …
Terrain & Heightmap Generation
Procedural terrain generation creates realistic landscapes using mathematical …
Trie (Prefix Tree)
A Trie (pronounced "try") is a tree-like data structure used to store …
Wave Function Collapse
Wave Function Collapse (WFC) is a procedural generation algorithm that creates …