Python quick sort
last modified November 18, 2026 Python 3.15
In this article we explain the quick sort algorithm in Python. We implement it with list comprehensions and in place with two partition schemes, look at its worst case, choose better pivots, handle duplicates with three-way partitioning, and use the same idea to find the k-th smallest element.
Quick sort, invented by Tony Hoare in 1959, is one of the fastest
general-purpose sorting algorithms and is used in many standard libraries,
usually in a hybrid form. Python's list.sort uses a merge-based
algorithm instead, because it must be stable.
Quick sort algorithm
Quick sort is a divide and conquer algorithm. It picks an element called the pivot and partitions the list: elements smaller than the pivot go before it, greater elements after it. The pivot is then in its final position, and the algorithm recursively sorts the two parts.
| Property | Value |
|---|---|
| Best and average case time | O(n log n) |
| Worst case time | O(n2), with consistently bad pivots |
| Extra space | O(log n) for the recursion, if the smaller part is sorted first |
| Stable | no (in-place versions) |
Quick sort example
The shortest Python implementation partitions the list with three list comprehensions.
def quick_sort(vals):
if len(vals) <= 1:
return vals
pivot = vals[len(vals) // 2]
less = [e for e in vals if e < pivot]
equal = [e for e in vals if e == pivot]
greater = [e for e in vals if e > pivot]
return quick_sort(less) + equal + quick_sort(greater)
nums = [10, 7, 8, 9, 1, 5, 7]
print(quick_sort(nums))
The middle element is the pivot. The elements are split into those less than, equal to, and greater than the pivot; only the first and the last group need further sorting. Collecting the equal elements separately handles duplicates such as the two sevens. This version is easy to read, but it creates new lists on every level of the recursion.
$ python quick_sort.py [1, 5, 7, 7, 8, 9, 10]
Lomuto partition
The in-place versions of quick sort rearrange the elements within the list. The Lomuto partition scheme uses the last element as the pivot.
def partition(vals, lo, hi):
pivot = vals[hi]
i = lo
for j in range(lo, hi):
if vals[j] < pivot:
vals[i], vals[j] = vals[j], vals[i]
i += 1
vals[i], vals[hi] = vals[hi], vals[i]
return i
def quick_sort(vals, lo=0, hi=None):
if hi is None:
hi = len(vals) - 1
if lo < hi:
p = partition(vals, lo, hi)
quick_sort(vals, lo, p - 1)
quick_sort(vals, p + 1, hi)
nums = [10, 80, 30, 90, 40, 50, 70]
quick_sort(nums)
print(nums)
The index i marks the end of the region of elements smaller
than the pivot. When j finds such an element, it is swapped
into this region and the region grows. Finally the pivot is swapped to
position i, between the two regions, and the function returns
its index. The recursive calls sort the parts on both sides of the pivot.
$ python lomuto.py [10, 30, 40, 50, 70, 80, 90]
Tracing the partitions
We print the pivot and the two parts after each partitioning, indented by the recursion depth.
def partition(vals, lo, hi):
pivot = vals[hi]
i = lo
for j in range(lo, hi):
if vals[j] < pivot:
vals[i], vals[j] = vals[j], vals[i]
i += 1
vals[i], vals[hi] = vals[hi], vals[i]
return i
def quick_sort(vals, lo, hi, depth=0):
if lo < hi:
pivot = vals[hi]
p = partition(vals, lo, hi)
print(f'{" " * depth}pivot {pivot:>2}: '
f'{vals[lo:p]} {vals[p]} {vals[p + 1:hi + 1]}')
quick_sort(vals, lo, p - 1, depth + 1)
quick_sort(vals, p + 1, hi, depth + 1)
nums = [10, 80, 30, 90, 40, 50, 70]
quick_sort(nums, 0, len(nums) - 1)
print(nums)
The pivot 70 splits the list well. In the left part, however,
the last element is always the largest, so each partition leaves one empty
part and the recursion goes one level deeper for every element. This hints
at the worst case of the algorithm.
$ python quick_trace.py
pivot 70: [10, 30, 40, 50] 70 [90, 80]
pivot 50: [10, 30, 40] 50 []
pivot 40: [10, 30] 40 []
pivot 30: [10] 30 []
pivot 80: [] 80 [90]
[10, 30, 40, 50, 70, 80, 90]
Hoare partition
The original Hoare scheme moves two indexes towards each other and swaps pairs of elements that are on the wrong sides. It makes fewer swaps than the Lomuto scheme.
def partition(vals, lo, hi):
pivot = vals[(lo + hi) // 2]
i, j = lo - 1, hi + 1
while True:
i += 1
while vals[i] < pivot:
i += 1
j -= 1
while vals[j] > pivot:
j -= 1
if i >= j:
return j
vals[i], vals[j] = vals[j], vals[i]
def quick_sort(vals, lo=0, hi=None):
if hi is None:
hi = len(vals) - 1
if lo < hi:
p = partition(vals, lo, hi)
quick_sort(vals, lo, p)
quick_sort(vals, p + 1, hi)
nums = [3, 7, 8, 5, 2, 1, 9, 5, 4]
quick_sort(nums)
print(nums)
words = ['sky', 'cup', 'forest', 'war', 'atom', 'cloud', 'tea']
quick_sort(words)
print(words)
The index i stops at an element not less than the pivot,
j at an element not greater than the pivot; the two elements
are swapped. When the indexes cross, j is the end of the left
part. Unlike Lomuto, the pivot is not necessarily at j, so the
recursion includes index p in the left part. Elements equal to
the pivot stop both indexes, so duplicates are spread over both parts.
$ python hoare.py [1, 2, 3, 4, 5, 5, 7, 8, 9] ['atom', 'cloud', 'cup', 'forest', 'sky', 'tea', 'war']
The worst case
With the last element as the pivot, a sorted list is the worst possible input. Every partition peels off a single element.
import random
import sys
class Stats:
comparisons = 0
depth = 0
def partition(vals, lo, hi, stats):
pivot = vals[hi]
i = lo
for j in range(lo, hi):
stats.comparisons += 1
if vals[j] < pivot:
vals[i], vals[j] = vals[j], vals[i]
i += 1
vals[i], vals[hi] = vals[hi], vals[i]
return i
def quick_sort(vals, lo, hi, stats, depth=1):
stats.depth = max(stats.depth, depth)
if lo < hi:
p = partition(vals, lo, hi, stats)
quick_sort(vals, lo, p - 1, stats, depth + 1)
quick_sort(vals, p + 1, hi, stats, depth + 1)
n = 500
rng = random.Random(6)
for name, data in [('random', rng.sample(range(n), n)),
('sorted', list(range(n)))]:
stats = Stats()
quick_sort(data, 0, n - 1, stats)
print(f'{name:<7} comparisons {stats.comparisons:>6} depth {stats.depth}')
print('recursion limit:', sys.getrecursionlimit())
try:
data = list(range(2000))
quick_sort(data, 0, len(data) - 1, Stats())
except RecursionError as e:
print('RecursionError:', e)
A random list of 500 elements needs fewer than 5000 comparisons and a
recursion depth of 20, close to log2500. The sorted list needs
n(n - 1)/2 = 124,750 comparisons and the recursion is as deep as the list is
long. For a sorted list of 2000 elements, the recursion exceeds the default
recursion limit of 1000 frames and Python raises a
RecursionError.
$ python worst_case.py random comparisons 4828 depth 20 sorted comparisons 124750 depth 500 recursion limit: 1000 RecursionError: maximum recursion depth exceeded
Choosing the pivot
Two common fixes for the worst case are the median of three, which uses the median of the first, middle, and last elements as the pivot, and a random pivot. We also recurse into the smaller part only and loop over the larger one, which keeps the recursion depth at O(log n).
import random
def median_of_three(vals, lo, hi):
mid = (lo + hi) // 2
if vals[mid] < vals[lo]:
vals[lo], vals[mid] = vals[mid], vals[lo]
if vals[hi] < vals[lo]:
vals[lo], vals[hi] = vals[hi], vals[lo]
if vals[mid] < vals[hi]:
vals[mid], vals[hi] = vals[hi], vals[mid]
def random_pivot(vals, lo, hi):
k = random.randint(lo, hi)
vals[k], vals[hi] = vals[hi], vals[k]
def quick_sort(vals, choose):
comparisons = 0
def sort(lo, hi):
nonlocal comparisons
while lo < hi:
choose(vals, lo, hi)
pivot = vals[hi]
i = lo
for j in range(lo, hi):
comparisons += 1
if vals[j] < pivot:
vals[i], vals[j] = vals[j], vals[i]
i += 1
vals[i], vals[hi] = vals[hi], vals[i]
if i - lo < hi - i:
sort(lo, i - 1)
lo = i + 1
else:
sort(i + 1, hi)
hi = i - 1
sort(0, len(vals) - 1)
return comparisons
random.seed(12)
n = 10_000
for name, data in [('sorted', list(range(n))),
('reversed', list(range(n, 0, -1)))]:
for choose in (median_of_three, random_pivot):
vals = data.copy()
count = quick_sort(vals, choose)
assert vals == sorted(data)
print(f'{name:<9}{choose.__name__:<16}{count:>8} comparisons')
The choose function moves the selected pivot to the last
position, so the Lomuto partition stays unchanged. The
while loop replaces the second recursive call. On 10,000 sorted
or reversed elements, the naive version would need almost 50 million
comparisons; both strategies stay close to n log2n, about
133,000. A random pivot gives the expected O(n log n) for any input, while
specially crafted inputs can still defeat the median of three.
$ python pivot_choice.py sorted median_of_three 113631 comparisons sorted random_pivot 153191 comparisons reversed median_of_three 218585 comparisons reversed random_pivot 144670 comparisons
Three-way partitioning
Lists with many duplicates are a problem for two-way partitioning: equal elements are compared and moved again and again. Three-way partitioning, known as the Dutch national flag problem, splits the list into elements less than, equal to, and greater than the pivot.
import random
def quick_sort_3way(vals, lo=0, hi=None):
if hi is None:
hi = len(vals) - 1
if lo >= hi:
return
pivot = vals[random.randint(lo, hi)]
lt, i, gt = lo, lo, hi
while i <= gt:
if vals[i] < pivot:
vals[lt], vals[i] = vals[i], vals[lt]
lt += 1
i += 1
elif vals[i] > pivot:
vals[i], vals[gt] = vals[gt], vals[i]
gt -= 1
else:
i += 1
quick_sort_3way(vals, lo, lt - 1)
quick_sort_3way(vals, gt + 1, hi)
random.seed(1)
colors = ['red', 'blue', 'green', 'blue', 'red', 'red', 'green', 'blue']
quick_sort_3way(colors)
print(colors)
grades = [random.choice('ABCDEF') for _ in range(100_000)]
quick_sort_3way(grades)
print(grades == sorted(grades), grades[:3], grades[-3:])
Elements before lt are less than the pivot, elements from
lt to i - 1 are equal, and elements after
gt are greater. The equal block is never touched again. A list
of 100,000 grades with only six distinct values is sorted after a few
partitions.
$ python three_way.py ['blue', 'blue', 'blue', 'green', 'green', 'red', 'red', 'red'] True ['A', 'A', 'A'] ['F', 'F', 'F']
Quickselect
The partition step can also find the k-th smallest element without sorting
the whole list. Quickselect partitions the list and continues only in the
part that contains index k. Its expected running time is
O(n).
import random
def quickselect(vals, k):
vals = vals.copy()
lo, hi = 0, len(vals) - 1
while True:
r = random.randint(lo, hi)
vals[r], vals[hi] = vals[hi], vals[r]
pivot = vals[hi]
i = lo
for j in range(lo, hi):
if vals[j] < pivot:
vals[i], vals[j] = vals[j], vals[i]
i += 1
vals[i], vals[hi] = vals[hi], vals[i]
if i == k:
return vals[i]
if k < i:
hi = i - 1
else:
lo = i + 1
salaries = [3200, 1800, 4100, 2500, 2900, 5600, 2100, 3800, 2700]
print('smallest:', quickselect(salaries, 0))
print('median: ', quickselect(salaries, len(salaries) // 2))
print('largest: ', quickselect(salaries, len(salaries) - 1))
print('check: ', sorted(salaries)[len(salaries) // 2])
After a partition, the pivot is at its final sorted index i.
If i equals k, we have the answer; otherwise we
continue on one side only. We find the smallest, the median, and the largest
salary and check the median against sorted.
$ python quickselect.py smallest: 1800 median: 2900 largest: 5600 check: 2900
Key functions and descending order
We add the key and reverse parameters to the list
comprehension version.
def quick_sort(vals, key=None, reverse=False):
if len(vals) <= 1:
return list(vals)
if key is None:
key = lambda e: e
pk = key(vals[len(vals) // 2])
less, equal, greater = [], [], []
for e in vals:
k = key(e)
if k < pk:
less.append(e)
elif k > pk:
greater.append(e)
else:
equal.append(e)
less = quick_sort(less, key, reverse)
greater = quick_sort(greater, key, reverse)
return greater + equal + less if reverse else less + equal + greater
cities = [('Bratislava', 475), ('Kosice', 229), ('Presov', 85),
('Zilina', 80), ('Nitra', 77), ('Trnava', 63)]
print(quick_sort(cities, key=lambda c: c[1]))
print(quick_sort(cities, key=lambda c: c[0], reverse=True))
The key is computed once per element and partition. For a descending order, the parts are concatenated in reverse. Because the elements are appended in their original order, this version is stable. We sort Slovak cities by population in thousands and then by name in descending order.
$ python quick_key.py
[('Trnava', 63), ('Nitra', 77), ('Zilina', 80), ('Presov', 85), ('Kosice', 229), ('Bratislava', 475)]
[('Zilina', 80), ('Trnava', 63), ('Presov', 85), ('Nitra', 77), ('Kosice', 229), ('Bratislava', 475)]
Benchmark
We compare the in-place quick sort with a random pivot, the list
comprehension version, and sorted.
import random
import timeit
def quick_sort(vals):
def sort(lo, hi):
while lo < hi:
k = random.randint(lo, hi)
vals[k], vals[hi] = vals[hi], vals[k]
pivot = vals[hi]
i = lo
for j in range(lo, hi):
if vals[j] < pivot:
vals[i], vals[j] = vals[j], vals[i]
i += 1
vals[i], vals[hi] = vals[hi], vals[i]
if i - lo < hi - i:
sort(lo, i - 1)
lo = i + 1
else:
sort(i + 1, hi)
hi = i - 1
sort(0, len(vals) - 1)
def quick_sort_lists(vals):
if len(vals) <= 1:
return vals
pivot = vals[len(vals) // 2]
return (quick_sort_lists([e for e in vals if e < pivot])
+ [e for e in vals if e == pivot]
+ quick_sort_lists([e for e in vals if e > pivot]))
rng = random.Random(10)
data = [rng.randint(0, 1_000_000) for _ in range(100_000)]
tests = [('in-place quick sort', lambda: quick_sort(data.copy())),
('list quick sort', lambda: quick_sort_lists(data)),
('sorted', lambda: sorted(data))]
for name, func in tests:
t = timeit.timeit(func, number=3) / 3
print(f'{name:<20} {t:.5f} s')
Both Python versions sort 100,000 numbers in roughly the same time; the
list comprehensions run fast but allocate many lists. The built-in
sorted is about ten times faster. The times vary between runs
and machines.
$ python benchmark.py in-place quick sort 0.12826 s list quick sort 0.14552 s sorted 0.01402 s
Source
Sorting Techniques – Python documentation
sys.setrecursionlimit – Python documentation
In this article we have implemented quick sort in Python with different partition schemes and pivot strategies. See also Python merge sort, Python heap sort, Python insertion sort, and Python sorted function.
Author
List all Python tutorials.