Quicksort

Quicksort is a divide and conquer sorting algorithm. It chooses a pivot value, partitions the array so that smaller elements go before the pivot and larger elements go after it, then recursively sorts both sides.

It is one of the most important practical sorting algorithms because it is fast in memory, has good cache behavior, and usually needs only logarithmic stack space. Its main weakness is that bad pivot choices can produce quadratic time.

Problem

Given an array $A$ of length $n$, reorder it such that:

$$ A[0] \le A[1] \le \dots \le A[n-1] $$

Idea

Choose a pivot $p$. Rearrange the array into three logical parts:

$$ \text{values } \le p,\quad p,\quad \text{values } \ge p $$

After partitioning, the pivot is in its final sorted position. The left and right parts can then be sorted independently.

Algorithm

quicksort(A, lo, hi):
    if lo >= hi:
        return

    p = partition(A, lo, hi)

    quicksort(A, lo, p - 1)
    quicksort(A, p + 1, hi)

One simple partition scheme is Lomuto partition.

partition(A, lo, hi):
    pivot = A[hi]
    i = lo

    for j from lo to hi - 1:
        if A[j] <= pivot:
            swap A[i] and A[j]
            i += 1

    swap A[i] and A[hi]
    return i

Example

Let:

$$ A = [4, 2, 7, 1, 5] $$

Choose pivot $5$.

Partition:

value	action
4	move left
2	move left
7	stay right
1	move left

After partition:

$$ [4, 2, 1, 5, 7] $$

The pivot $5$ is now fixed. Recursively sort:

$$ [4, 2, 1] $$

and

$$ [7] $$

Final result:

$$ [1, 2, 4, 5, 7] $$

Correctness

Partition places the pivot into a position where every element on its left is less than or equal to the pivot and every element on its right is greater than or equal to the pivot. The pivot therefore has its final sorted position.

The recursive calls sort the left and right subarrays. Since all left elements are no larger than the pivot and all right elements are no smaller than the pivot, combining the sorted left side, the pivot, and the sorted right side gives a sorted array.

Complexity

case	time
best	$O(n \log n)$
average	$O(n \log n)$
worst	$O(n^2)$

The worst case occurs when partitions are extremely unbalanced, for example when the pivot is repeatedly the smallest or largest element.

Space usage comes from recursion:

case	space
balanced recursion	$O(\log n)$
worst recursion	$O(n)$

Properties

property	value
stable	no
in-place	yes
comparison based	yes
adaptive	no
cache behavior	good

Notes

Quicksort is fast in practice, but raw quicksort should be protected against bad pivots. Common improvements include randomized pivots, median of three selection, three way partitioning for duplicate heavy arrays, and introsort fallback to heapsort.

Implementation

def quicksort(a):
    def sort(lo, hi):
        if lo >= hi:
            return

        p = partition(lo, hi)
        sort(lo, p - 1)
        sort(p + 1, hi)

    def partition(lo, hi):
        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]
        return i

    sort(0, len(a) - 1)
    return a

func QuickSort(a []int) {
	var sort func(int, int)

	sort = func(lo, hi int) {
		if lo >= hi {
			return
		}

		p := partition(a, lo, hi)
		sort(lo, p-1)
		sort(p+1, hi)
	}

	sort(0, len(a)-1)
}

func partition(a []int, lo, hi int) int {
	pivot := a[hi]
	i := lo

	for 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]
	return i
}