Quicksort is a divide-and-conquer comparison sort that picks a pivot, partitions the array around it, and recursively sorts the partitions. In practice it is the fastest general-purpose sort on most inputs, which is why it underlies std::sort in C++ and many language standard libraries.
| Best | Average | Worst | Space (Worst) |
|---|---|---|---|
Ω(n log n) |
Θ(n log n) |
O(n²) |
O(log n) |
Pick a pivot (commonly the last, first, or a random element). Partition: move all elements ≤ pivot to the left, all > pivot to the right. Recurse on each side. Worst case O(n²) hits when pivots are consistently extreme (e.g. already-sorted input with a fixed last-element pivot); randomization or median-of-three avoids this in practice.
def quicksort(arr):
"""In-place Lomuto-partition quicksort."""
def _sort(lo, hi):
if lo >= hi:
return
pivot = arr[hi]
i = lo
for j in range(lo, hi):
if arr[j] <= pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[hi] = arr[hi], arr[i]
_sort(lo, i - 1)
_sort(i + 1, hi)
_sort(0, len(arr) - 1)
return arr
print(quicksort([3, 6, 1, 8, 2, 9, 4])) # [1, 2, 3, 4, 6, 8, 9]Partitioning is the whole algorithm; the recursion just applies it to smaller ranges. In the Lomuto scheme shown above, the last element is the pivot, an index i marks the end of the "less than pivot" region, and a second index j scans the array. Each element smaller than the pivot is swapped into position i and the region grows. After the scan, the pivot is swapped into position i, which is its final sorted position. Everything left of it is smaller and everything right of it is greater or equal, so the two sides can be sorted independently.
Hoare's original scheme uses two indices moving toward each other and swaps out-of-place pairs. It performs about three times fewer swaps on average and handles many equal keys better, but the pivot does not necessarily end in its final place, so the recursion bounds differ slightly.
When the pivot splits the range roughly in half, the recursion depth is about log2 n and each level does O(n) work, giving O(n log n). When the pivot is always the smallest or largest element, for example choosing the last element of an already sorted array, one side is empty at every level and the cost becomes O(n^2) with recursion depth n. Randomized or median-of-three pivot selection makes that case extremely unlikely in practice. Recursing into the smaller side first and looping on the larger side bounds the stack to O(log n) even in bad cases.
import random
def quicksort3(a, lo=0, hi=None):
"""In-place, randomized, three-way (Dutch flag) partition."""
if hi is None:
hi = len(a) - 1
while lo < hi:
p = a[random.randint(lo, hi)]
lt, i, gt = lo, lo, hi
while i <= gt:
if a[i] < p:
a[lt], a[i] = a[i], a[lt]; lt += 1; i += 1
elif a[i] > p:
a[i], a[gt] = a[gt], a[i]; gt -= 1
else:
i += 1
# a[lo:lt] < p, a[lt:gt+1] == p, a[gt+1:hi+1] > p
if lt - lo < hi - gt:
quicksort3(a, lo, lt - 1); lo = gt + 1 # recurse on smaller side
else:
quicksort3(a, gt + 1, hi); hi = lt - 1
data = [5, 3, 8, 3, 1, 9, 3, 2]
quicksort3(data)
print(data) # [1, 2, 3, 3, 3, 5, 8, 9]The three-way partition groups all keys equal to the pivot in the middle and never recurses into them, so an array with many duplicates sorts in close to linear time instead of degrading.
For small subarrays, typically below 10 to 20 elements, production implementations stop recursing and finish with insertion sort, which has lower overhead on tiny inputs.
| Algorithm | Best | Average | Worst | Extra space | Stable |
|---|---|---|---|---|---|
| Quicksort | O(n log n) | O(n log n) | O(n^2) | O(log n) | No |
| Mergesort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes |
Introsort, used by many C++ standard libraries, starts with quicksort and switches to heapsort if recursion depth exceeds a multiple of log n, which keeps quicksort's speed while guaranteeing O(n log n). Python's built-in sorted uses Timsort instead because stability and fast handling of partially sorted data matter more for general use.
Test any custom implementation on sorted, reverse-sorted, all-equal, and random inputs; those four cases expose nearly every partitioning bug.