ZetCode

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.

PropertyValue
Best and average case timeO(n log n)
Worst case timeO(n2), with consistently bad pivots
Extra spaceO(log n) for the recursion, if the smaller part is sorted first
Stableno (in-place versions)

Quick sort example

The shortest Python implementation partitions the list with three list comprehensions.

quick_sort.py
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.

lomuto.py
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.

quick_trace.py
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.

hoare.py
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.

worst_case.py
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).

pivot_choice.py
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.

three_way.py
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).

quickselect.py
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.

quick_key.py
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.

benchmark.py
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

I am Jan Bodnar, a programmer and technical writer. I have been writing programming tutorials at ZetCode since 2007 and have published eight e-books. See about the author.

List all Python tutorials.