Quick Sort

#How does it work?

Quick sort also uses "divide and conquer", but does most of its work while dividing. It picks an element as the pivot.

In the partition step, elements smaller than the pivot are gathered on the left and larger or equal ones on the right. Finally the pivot goes between them, which is its final position.

Then the parts to the left and right of the pivot are sorted the same way. This animation uses Lomuto partitioning, where the pivot is always the last element of the range.

#Live animation

quickSort(a, lo, hi):
  if lo >= hi: return
  pivot = a[hi]; i = lo
  for j = lo to hi - 1
    if a[j] < pivot: swap(a[i], a[j]); i = i + 1
  swap(a[i], a[hi])
  quickSort(a, lo, i - 1); quickSort(a, i + 1, hi)

#Step by step

1. 01If the range has one element or none, it is already sorted; return.
2. 02Pick a pivot (here: the last element of the range).
3. 03Scan the range: move every element smaller than the pivot behind the left-side boundary.
4. 04After the scan, put the pivot right after the smaller elements; it is now in its final place.
5. 05Sort the parts left and right of the pivot the same way.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

def partition(a: list[int], lo: int, hi: int) -> int:
    """Lomuto partition: the last element is the pivot. Returns its final index."""
    pivot = a[hi]
    i = lo  # a[lo:i] holds the elements smaller than the pivot
    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]
    return i


def quick_sort(a: list[int], lo: int, hi: int) -> None:
    if lo >= hi:
        return
    p = partition(a, lo, hi)
    quick_sort(a, lo, p - 1)
    quick_sort(a, p + 1, hi)


numbers = [5, 1, 4, 2, 8, 3]
quick_sort(numbers, 0, len(numbers) - 1)
print(*numbers)

#Complexity

When the pivot splits the array into roughly equal halves, it takes n log n operations. If the pivot is always the smallest or largest element (e.g. picking the last element of a sorted array), the parts are unbalanced and time grows to O(n²). A random pivot or "median of three" practically removes this risk. The recursion stack uses O(log n) memory on average.

#When to use it?

Usually the fastest comparison sort in practice: it works in place and uses the cache well. C's qsort and many languages' sorting of number arrays are based on quick sort (often as hybrids like introsort). When you need stability or a worst-case guarantee, prefer merge sort.

#Practice

Log in to answer questions and save your progress.