home

# Quicksort

Quicksort selects a ‘pivot’ element from the array then partitions the remaining elements into ‘less than’ and ‘greater than’ sub-arrays. Each of these partitions are then recursively sorted in the same way.

The selection of the pivot element and associated partition methods vary, with quicksort best though of a class of algorithms based around the high-level divide and conquer structure.

## Algorithm

QSORT(A):
IF A has only one item THEN
RETURN A
ELSE
pivot ← middle item of A (or other pivot scheme)
left  ← all A < pivot
right ← all A > pivot
RETURN [QSORT(left) + pivot + QSORT(right)]

## Performance

Worst Average Best
Time $$O(n^2)$$ $$O(n \log n)$$ $$O(n \log n)$$
Space $$O(n)$$