Quick Sort Explained: Partitioning, Code & Complexity

Quick sort is a divide-and-conquer sort built around partitioning: pick a pivot element, rearrange the array so everything smaller is on its left and everything larger is on its right, then recursively sort the two sides. It is in-place and, on average, the fastest comparison sort in practice — but a careless pivot choice can degrade it to O(n²).

The idea

Choose a pivot from the array.
Partition: move all elements less than the pivot before it and all greater after it. The pivot is now in its final sorted position.
Recurse on the left part and the right part. Subarrays of size 0 or 1 are the base case.

Unlike merge sort, there is no separate combine step — once both sides are sorted, the whole array is sorted, because partitioning already placed the pivot correctly.

Implementation

This uses the Lomuto partition scheme (pivot = last element) for clarity. We swap a random element to the end first, which avoids the O(n²) trap on already-sorted input.

int partition(std::vector<int>& a, int lo, int hi) {
    std::swap(a[lo + rand() % (hi - lo + 1)], a[hi]); // randomize pivot
    int pivot = a[hi], i = lo;
    for (int j = lo; j < hi; j++)
        if (a[j] < pivot) std::swap(a[i++], a[j]);
    std::swap(a[i], a[hi]);   // pivot to its final spot
    return i;
}

void quickSort(std::vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(a, lo, hi);
    quickSort(a, lo, p - 1);
    quickSort(a, p + 1, hi);
}

int partition(int[] a, int lo, int hi) {
    int r = lo + (int)(Math.random() * (hi - lo + 1));
    int t0 = a[r]; a[r] = a[hi]; a[hi] = t0; // randomize pivot
    int pivot = a[hi], i = lo;
    for (int j = lo; j < hi; j++)
        if (a[j] < pivot) { int t = a[i]; a[i] = a[j]; a[j] = t; i++; }
    int t = a[i]; a[i] = a[hi]; a[hi] = t;   // pivot to its final spot
    return i;
}

void quickSort(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(a, lo, hi);
    quickSort(a, lo, p - 1);
    quickSort(a, p + 1, hi);
}

function quickSort(a, lo = 0, hi = a.length - 1) {
  if (lo >= hi) return;
  // partition (Lomuto, randomized pivot)
  const r = lo + Math.floor(Math.random() * (hi - lo + 1));
  [a[r], a[hi]] = [a[hi], a[r]];
  const pivot = a[hi];
  let i = lo;
  for (let j = lo; j < hi; j++)
    if (a[j] < pivot) { [a[i], a[j]] = [a[j], a[i]]; i++; }
  [a[i], a[hi]] = [a[hi], a[i]]; // pivot to its final spot
  quickSort(a, lo, i - 1);
  quickSort(a, i + 1, hi);
}

import random

def quick_sort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo >= hi:
        return
    # partition (Lomuto, randomized pivot)
    r = random.randint(lo, hi)
    a[r], a[hi] = a[hi], a[r]
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]   # pivot to its final spot
    quick_sort(a, lo, i - 1)
    quick_sort(a, i + 1, hi)

Complexity

Case	Time	When
Best	O(n log n)	pivot splits evenly each time
Average	O(n log n)	random data / random pivot
Worst	O(n²)	pivot is always the min or max (e.g. sorted input with a fixed end pivot)

Space: O(log n) average for the recursion stack (O(n) in the worst case). It needs no merge buffer, so it sorts genuinely in place.
Stable: no — partitioning swaps distant elements and can reorder equal keys.

Gotcha: Choosing the first or last element as a fixed pivot makes already-sorted input the worst case — every partition peels off just one element, giving O(n²). Randomizing the pivot (as above) or using the median-of-three makes that worst case astronomically unlikely.

When to use it

Quick sort is the default in-memory sort in many standard libraries (often as introsort — quick sort that switches to heap sort if recursion goes too deep, guaranteeing O(n log n), and to insertion sort for tiny subarrays). Reach for it when you want the fastest average in-place sort and don’t need stability. If you need stability or a hard worst-case guarantee, prefer merge sort. See the comparison page.

Next: Heap Sort.