Quick Sort

Overview

Quick Sort is a divide-and-conquer sorting algorithm that picks a pivot element and partitions the array around the pivot. Elements smaller than the pivot are placed before it, and elements greater than the pivot are placed after it. This process is repeated recursively for the sub-arrays.

Quick Sort is one of the most widely used sorting algorithms due to its excellent average-case performance of O(n log n). However, it has a worst-case time complexity of O(n²), which occurs when the pivot is always the smallest or largest element.

How It Works

The algorithm follows these steps:

  1. Choose Pivot: Select an element from the array as the pivot
  2. Partition: Rearrange the array so that all elements less than the pivot come before it, and all elements greater come after it
  3. Recurse: Apply the same process recursively to the sub-arrays on both sides of the pivot

The pivot selection is crucial. Common strategies include choosing the first element, last element, middle element, or a random element. The partition step ensures that after partitioning, the pivot is in its final sorted position.

Algorithm


QuickSort(arr, low, high):
    if low < high:
        pivot_index = Partition(arr, low, high)
        QuickSort(arr, low, pivot_index - 1)
        QuickSort(arr, pivot_index + 1, high)

Partition(arr, low, high):
    pivot = arr[high]  # Choose last element as pivot
    i = low - 1
    
    for j = low to high - 1:
        if arr[j] <= pivot:
            i = i + 1
            swap arr[i] and arr[j]
    
    swap arr[i + 1] and arr[high]
    return i + 1

Implementation


def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]
    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)

# In-place version
def quick_sort_inplace(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        quick_sort_inplace(arr, low, pivot_index - 1)
        quick_sort_inplace(arr, pivot_index + 1, high)

def partition(arr, low, high):
    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

Complexity Analysis

  • Time Complexity:
    • Best Case: O(n log n) - when pivot divides array evenly
    • Average Case: O(n log n) - expected performance
    • Worst Case: O(n²) - when pivot is always smallest/largest
  • Space Complexity: O(log n) for recursion stack (average case), O(n) worst case

The worst case occurs when the array is already sorted and we always pick the first or last element as pivot. This can be avoided by using randomized pivot selection or median-of-three pivot selection.

Characteristics

  • Stable: No - does not preserve relative order of equal elements
  • In-place: Yes (with in-place implementation) - can be done with O(log n) extra space
  • Adaptive: No — and in fact performance depends heavily on input order for any deterministic pivot rule. With last-element pivots, already-sorted input is the worst case. Randomizing the pivot removes the dependence on input order, which is precisely why it is standard.
  • Online: No - requires the entire array to be present

When to Use Quick Sort

Quick Sort is an excellent choice when:

  • Average-case performance is more important than worst-case guarantee
  • You need in-place sorting with good average performance
  • Stability is not required
  • You can use randomized pivot selection to avoid worst-case scenarios
  • General-purpose sorting where data distribution is unknown

Pivot Selection Strategies

  • First/Last Element: Simple but can lead to worst-case O(n²)
  • Middle Element: Better than first/last, but still can be problematic
  • Random Element: Reduces probability of worst-case, good for general use
  • Median-of-Three: Choose median of first, middle, and last elements - good balance in practice, but still deterministic and therefore still defeatable by a crafted input
  • Median-of-Medians: Guarantees a pivot in the middle 30–70% of the range in O(n), making the worst case O(n log n). The constants are poor enough that it is rarely used for sorting, though it is the basis of deterministic selection (quickselect).

Three Problems the Basic Version Has

The Lomuto partition above is the clearest to teach, but it has real weaknesses worth knowing before you use quicksort in anger.

1. Duplicate elements. On an array where every element is equal, Lomuto puts all of them on one side of the pivot, giving a maximally unbalanced split and O(n²) behaviour on what should be the easiest possible input. The fix is three-way partitioning (the Dutch national flag algorithm), which separates the array into < pivot, = pivot, and > pivot, and recurses only on the outer two. With many duplicates this turns O(n²) into O(n).

2. Swap count. Hoare's original partition scheme, which walks two pointers inward from both ends, performs roughly three times fewer swaps than Lomuto. It is fiddlier to get right — the returned index is not the pivot's final position — but it is what production implementations actually use.

3. Adversarial input. A deterministic pivot rule means an attacker who knows your implementation can construct input that forces O(n²). This is a genuine denial-of-service vector, and it has been exploited against real systems. Randomize the pivot, or use introsort.

What Production Sorts Actually Do: Introsort

No serious standard library ships bare quicksort. Introsort (Musser, 1997) resolves the quicksort/heapsort tension by combining three algorithms:

  1. Run quicksort, which is fast in the common case.
  2. Track recursion depth. If it exceeds ~2 log n — a signal that pivots are going badly — switch that subarray to heap sort, guaranteeing O(n log n).
  3. On subarrays below ~16 elements, stop recursing and finish with insertion sort, which wins at small sizes on cache behaviour and low overhead.

The result keeps quicksort's average-case speed while making the O(n²) worst case unreachable. This is what C++ std::sort does. Rust's sort_unstable and Go's sort (since 1.19) use pdqsort (pattern-defeating quicksort), a further refinement that adds three-way partitioning for duplicates and detects already-sorted runs.

Example

Sorting [10, 7, 8, 9, 1, 5] with pivot as last element: 

Initial: [10, 7, 8, 9, 1, 5]     pivot = arr[high] = 5

Lomuto partition, walking j from low to high-1 and swapping into position i+1
whenever arr[j] <= pivot:

  i=-1  j=0: 10 <= 5? no
        j=1:  7 <= 5? no
        j=2:  8 <= 5? no
        j=3:  9 <= 5? no
        j=4:  1 <= 5? YES -> i=0, swap arr[0],arr[4]  ->  [1, 7, 8, 9, 10, 5]
  finally swap arr[i+1] with the pivot: swap arr[1],arr[5]

  Result: [1, 5, 8, 9, 10, 7]     pivot 5 now at index 1, its final position
           ^^^   ^^^^^^^^^^^
          < 5      > 5  (unordered among themselves)

Recurse left on [1]              -> already sorted (single element)
Recurse right on [8, 9, 10, 7]   -> pivot = 7
  8<=7? no   9<=7? no   10<=7? no
  swap arr[i+1] with pivot       -> [7, 9, 10, 8]
  Recurse on [] and [9, 10, 8]   -> pivot = 8 -> [8, 10, 9] -> ... -> [8, 9, 10]

Final: [1, 5, 7, 8, 9, 10]

Note that partitioning does not sort the two sides — it only guarantees that everything left of the pivot is ≤ it and everything right is > it. The pivot itself is in its final position and is never moved again; that is the invariant the recursion relies on.

Related Algorithms

Explore other sorting algorithms: