Skip to content
Laviyx Learn

Try

DSA course menu

Quick Sort in Python: Partitioning, Pivots and Quickselect

Learn quick sort: choosing a pivot, the Lomuto partition scheme, in-place recursive sorting, why it is O(n log n) on average but O(n²) in the worst case, random pivots, and quickselect for the kth smallest item.

Intermediate11 min readUpdated
On this page

Quick sort is another divide and conquer sort, but it does its work before recursing:

  1. Pick a pivot item.
  2. Partition: rearrange the list so everything smaller than the pivot is on its left and everything larger is on its right. The pivot is now in its final position.
  3. Recursively sort the left part and the right part.

There is no merge step: once both sides are sorted, the whole list is.

A simple (not in-place) version#

This version shows the idea clearly, at the cost of building new lists:

Python
def quick_sort_simple(items):
    if len(items) <= 1:
        return items
    pivot = items[len(items) // 2]
    smaller = [x for x in items if x < pivot]
    equal = [x for x in items if x == pivot]
    larger = [x for x in items if x > pivot]
    return quick_sort_simple(smaller) + equal + quick_sort_simple(larger)

print(quick_sort_simple([3, 6, 8, 10, 1, 2, 1]))
Output
[1, 1, 2, 3, 6, 8, 10]

In-place partitioning (Lomuto scheme)#

The real algorithm partitions within the list itself, using O(1) extra memory per call. Take the last item as the pivot; walk the list keeping a boundary i: everything before i is smaller than the pivot.

Python
def partition(items, low, high):
    pivot = items[high]
    i = low                          # next slot for a "small" item
    for j in range(low, high):
        if items[j] < pivot:
            items[i], items[j] = items[j], items[i]
            i += 1
    items[i], items[high] = items[high], items[i]   # pivot into place
    return i

data = [10, 80, 30, 90, 40, 50, 70]
p = partition(data, 0, len(data) - 1)
print(data, "pivot index", p)
Output
[10, 30, 40, 50, 70, 90, 80] pivot index 4

The pivot 70 is now at index 4; everything to its left is smaller and everything to its right is larger.

The full in-place sort#

Python
import random

def partition(items, low, high):
    pivot = items[high]
    i = low
    for j in range(low, high):
        if items[j] < pivot:
            items[i], items[j] = items[j], items[i]
            i += 1
    items[i], items[high] = items[high], items[i]
    return i

def quick_sort(items, low=0, high=None):
    if high is None:
        high = len(items) - 1
    if low < high:
        p = partition(items, low, high)
        quick_sort(items, low, p - 1)
        quick_sort(items, p + 1, high)

data = [10, 80, 30, 90, 40, 50, 70]
quick_sort(data)
print(data)

random.seed(3)
for _ in range(100):
    xs = [random.randint(0, 50) for _ in range(random.randint(0, 30))]
    expected = sorted(xs)
    quick_sort(xs)
    assert xs == expected
print("100 random lists sorted correctly")
Output
[10, 30, 40, 50, 70, 80, 90]
100 random lists sorted correctly

Good and bad pivots#

If each pivot splits the list roughly in half, there are log n levels of O(n) partitioning: O(n log n). If the pivot is always the smallest or largest item, each partition only removes one item: n levels, O(n²).

Choosing the last item as the pivot hits the worst case on input that is already sorted. Counting comparisons shows it:

Python
import random, sys
sys.setrecursionlimit(5000)

comparisons = 0

def partition(items, low, high, randomize):
    global comparisons
    if randomize:
        r = random.randint(low, high)
        items[r], items[high] = items[high], items[r]
    pivot, i = items[high], low
    for j in range(low, high):
        comparisons += 1
        if items[j] < pivot:
            items[i], items[j] = items[j], items[i]
            i += 1
    items[i], items[high] = items[high], items[i]
    return i

def quick_sort(items, low, high, randomize):
    if low < high:
        p = partition(items, low, high, randomize)
        quick_sort(items, low, p - 1, randomize)
        quick_sort(items, p + 1, high, randomize)

random.seed(11)
n = 2000
for label, randomize in [("last-item pivot", False), ("random pivot", True)]:
    comparisons = 0
    data = list(range(n))            # already sorted input
    quick_sort(data, 0, n - 1, randomize)
    print(f"{label:>16}: {comparisons:>8} comparisons on sorted input")
Output
 last-item pivot:  1999000 comparisons on sorted input
    random pivot:    24065 comparisons on sorted input

A random pivot makes the bad case extremely unlikely for any input, giving O(n log n) on average. (The setrecursionlimit call is needed only because the bad pivot recurses n levels deep.)

PropertyQuick sort
average timeO(n log n)
worst timeO(n²) (rare with random pivots)
extra spaceO(log n) recursion stack on average
stableno

Quick sort is usually faster than merge sort in practice because it sorts in place and works on neighbouring memory; C's qsort and C++'s std::sort use variants of it.

Quickselect: the kth smallest item#

To find the kth smallest item you do not need to sort everything. Partition once; the pivot lands at its final index p. If p == k, done. Otherwise recurse into only one side:

Python
import random

def quickselect(items, k):
    items = items[:]
    low, high = 0, len(items) - 1
    while True:
        r = random.randint(low, high)
        items[r], items[high] = items[high], items[r]
        pivot, i = items[high], low
        for j in range(low, high):
            if items[j] < pivot:
                items[i], items[j] = items[j], items[i]
                i += 1
        items[i], items[high] = items[high], items[i]
        if i == k:
            return items[i]
        if i < k:
            low = i + 1
        else:
            high = i - 1

data = [7, 10, 4, 3, 20, 15]
print([quickselect(data, k) for k in range(len(data))])
print(sorted(data))
Output
[3, 4, 7, 10, 15, 20]
[3, 4, 7, 10, 15, 20]

Each round discards one side, so the average work is n + n/2 + n/4 + … ≈ 2n: O(n) on average.

Common mistakes#

Practice#

Practice exercise

Many equal values make Lomuto partitioning slow. Write sort_colors(nums) that sorts a list containing only 0s, 1s and 2s in one pass and in place, using a three-way partition (the "Dutch national flag" problem).

Show hint

Keep three pointers: low (next place for a 0), mid (current item) and high (next place for a 2, from the end). A 0 swaps to low, a 2 swaps to high, and a 1 just moves mid forward. Do not advance mid after swapping with high: the item that came back has not been checked.

Show solution
Python
def sort_colors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 2:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
        else:
            mid += 1
    return nums

print(sort_colors([2, 0, 2, 1, 1, 0]))
print(sort_colors([2, 1, 0]))
Output
[0, 0, 1, 1, 2, 2]
[0, 1, 2]

Three-way partitioning is also what keeps quick sort fast on lists with many duplicates.

Key takeaway#

Next: sorting without comparisons, in Counting and Radix Sort.

Finished this lesson?

Related lessons

DSAMerge Sort in Python: Divide and Conquer ExplainedLearn merge sort: splitting a list in half, sorting each half recursively, merging two sorted lists, why it is O(n log n), its O(n) memory cost, and counting inversions with merge sort.Intermediate10 min readDSABubble Sort, Selection Sort and Insertion Sort in PythonLearn the three simple O(n²) sorting algorithms with Python code, step-by-step traces and comparison counts, plus what stable sorting means and when insertion sort is actually fast.Intermediate10 min readDSAHeaps and Priority Queues in Python (heapq Explained)Learn the heap data structure: min-heaps and max-heaps, storing a complete tree in an array, sift up and sift down, building a heap in O(n), Python's heapq module, heap sort and top-k problems.Intermediate10 min readDSARecursion for DSA: Base Cases, Call Stack and MemoizationUnderstand recursion for data structures and algorithms: base and recursive cases, how the call stack works, recursion trees, the cost of naive Fibonacci, and memoization with lru_cache.Beginner9 min read