Python Quicksort

Quicksort is one of the most widely used sorting algorithms in computer science, prized for its speed and elegant recursive design. Instead of comparing every pair of elements, it picks a “pivot” value and rearranges the list so everything smaller ends up on one side and everything larger ends up on the other. It then recursively repeats this process on each side until the whole list is sorted. Python’s built-in sort() and sorted() actually use a different algorithm (Timsort), but Quicksort remains essential to learn because it teaches divide-and-conquer thinking, in-place partitioning, and how average-case and worst-case performance can differ dramatically for the same algorithm.

Overview / How it works

Quicksort is a divide-and-conquer algorithm. It solves the sorting problem by breaking it into smaller subproblems of the same shape, solving those recursively, and combining the results. The three steps are always the same:

• Choose a pivot — pick one element from the list to act as a dividing line.
• Partition — rearrange the list so every element less than the pivot comes before it, and every element greater comes after it. After partitioning, the pivot sits at its final sorted position.
• Recurse — apply the same process to the sublist left of the pivot and the sublist right of the pivot. The base case is a list of 0 or 1 elements, which is already sorted.

Under the hood, a Python list is an array of references (pointers) to objects, not a contiguous block of raw values. This matters for Quicksort in two ways. First, an in-place implementation swaps references inside the same underlying array — it does not copy the objects themselves, so swapping is cheap regardless of how large the elements are. Second, a purely functional implementation (one that builds new lists with <, ==, and > comparisons) allocates brand-new list objects at every recursive call, which is simpler to read but costs extra memory and time compared to an in-place version.

Quicksort is not stable: two equal elements are not guaranteed to keep their original relative order, because partitioning only cares about ordering relative to the pivot, not relative to each other. If you need stability, use Python’s built-in sorted() (Timsort is stable) instead of a hand-rolled Quicksort.

Performance depends heavily on how the pivot is chosen. On average, across random inputs, Quicksort runs in O(n log n) time: each partition step is O(n), and the recursion tree has O(log n) levels because a “good” pivot roughly halves the list each time. In the worst case — for example, always picking the first or last element as the pivot on an already-sorted list — each partition only shrinks the list by one element, giving O(n²) time and O(n) recursion depth. This is the single biggest practical risk when implementing Quicksort yourself, and it’s why real-world implementations use randomized or median-of-three pivot selection.

Syntax

There is no built-in quicksort() keyword in Python — you write it yourself as a recursive function. The general shape looks like this:

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = choose_pivot(arr)
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

Part	Purpose
len(arr) <= 1	Base case: an empty or single-element list is already sorted.
choose_pivot(arr)	Selects the dividing value; strategy affects performance, not correctness.
left / middle / right	The three partitions relative to the pivot.
quicksort(left) + middle + quicksort(right)	Recursively sort each side, then concatenate in order.

An in-place version instead uses index bounds (low, high) and swaps elements within a single list, which is more memory-efficient but trickier to get right.

Examples

Example 1: A simple functional Quicksort

This version is the easiest to understand: it builds new lists instead of sorting in place.

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

numbers = [8, 3, 1, 7, 0, 10, 2]
sorted_numbers = quicksort(numbers)
print(sorted_numbers)

Output:

[0, 1, 2, 3, 7, 8, 10]

The pivot is taken from the middle index. Every element smaller than the pivot goes into left, everything equal goes into middle (handling duplicates cleanly), and everything larger goes into right. The two sides are sorted recursively, and the final result is left + middle + right concatenated in order.

Example 2: In-place Quicksort with Lomuto partitioning

Production-quality Quicksort sorts the list in place instead of allocating new lists at every step.

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

def quicksort_inplace(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        pivot_index = partition(arr, low, high)
        quicksort_inplace(arr, low, pivot_index - 1)
        quicksort_inplace(arr, pivot_index + 1, high)

data = [29, 10, 14, 37, 13]
quicksort_inplace(data)
print(data)

Output:

[10, 13, 14, 29, 37]

This uses the Lomuto partition scheme: the last element becomes the pivot, and i tracks the boundary of the “smaller than pivot” region as j scans through the rest. After the loop, the pivot is swapped into position i + 1, which is its correct sorted index. quicksort_inplace then recurses on the left and right sub-ranges using index bounds only — no new lists are created, so this is more memory-efficient than Example 1.

Example 3: Sorting objects with a key function

Real-world sorting usually needs to order complex objects by some attribute, not just plain numbers. Adding a key parameter makes Quicksort just as flexible as sorted(key=...).

def quicksort_key(arr, key=lambda x: x):
    if len(arr) <= 1:
        return arr
    pivot = key(arr[len(arr) // 2])
    left = [x for x in arr if key(x) < pivot]
    middle = [x for x in arr if key(x) == pivot]
    right = [x for x in arr if key(x) > pivot]
    return quicksort_key(left, key) + middle + quicksort_key(right, key)

students = [
    {"name": "Riya", "score": 82},
    {"name": "Tom", "score": 67},
    {"name": "Zara", "score": 91},
    {"name": "Liam", "score": 74},
]

ranked = quicksort_key(students, key=lambda s: s["score"])
for student in ranked:
    print(f"{student['name']}: {student['score']}")

Output:

Tom: 67
Liam: 74
Riya: 82
Zara: 91

Instead of comparing elements directly, every comparison goes through key(x), so the pivot is the pivot student’s score, not the whole dictionary. This pattern — comparing on a derived value rather than the element itself — is exactly what sorted(iterable, key=...) does internally, and it’s the standard way to make a sorting routine reusable for any data shape.

Under the hood: step by step

Walking through the Lomuto partition from Example 2 on [29, 10, 14, 37, 13] shows exactly what happens:

• The pivot is arr[high], which is 13. The pointer i starts at -1 (one before the range).
• j walks from low to high - 1. Whenever arr[j] <= pivot, i advances and the two elements swap — this pushes small elements toward the front of the current range.
• Only 10 is <= 13, so after the loop the array is [10, 29, 14, 37, 13] with i = 0.
• The final swap places the pivot right after the small elements: swapping index 1 with index 4 gives [10, 13, 14, 37, 29]. The pivot 13 is now at index 1, its correct sorted position.
• Quicksort recurses on the left range (index 0 to 0, already trivially sorted) and the right range (index 2 to 4, [14, 37, 29]), repeating the same process until every range has 0 or 1 elements.

Each recursive call does O(n) work in its own partition step, and because a well-chosen pivot roughly halves the range every time, the recursion tree has O(log n) levels — giving the familiar O(n log n) average case.

Common Mistakes

Mistake 1: Always using a fixed pivot (first or last element)

Picking the first or last element as the pivot every time is simple, but it silently degrades to O(n²) on inputs that are already sorted, reverse-sorted, or contain many duplicates — exactly the kind of data that shows up often in practice.

def quicksort_naive(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]  # always the first element
    left = [x for x in arr[1:] if x < pivot]
    right = [x for x in arr[1:] if x >= pivot]
    return quicksort_naive(left) + [pivot] + quicksort_naive(right)

On a sorted list, left is always empty and right shrinks by exactly one element per call, producing n recursive calls instead of log n — both slow and, for large inputs, capable of hitting Python’s recursion limit. The fix is to randomize the pivot (or use median-of-three: compare the first, middle, and last elements and pick the median) so worst-case inputs become statistically very unlikely:

import random

def quicksort_random(arr):
    if len(arr) <= 1:
        return arr
    pivot = random.choice(arr)
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort_random(left) + middle + quicksort_random(right)

Mistake 2: Forgetting to swap the pivot into place

In the Lomuto partition scheme, the pivot must be swapped from the end of the range into position i + 1 after the loop finishes. Skipping this step is a very common bug that leaves the pivot in the wrong place and produces an incorrectly sorted list.

def partition_buggy(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    return i + 1  # BUG: pivot was never moved out of arr[high]

Because the pivot never leaves its original position at high, the returned index doesn’t actually correspond to the pivot’s location, and later recursive calls will re-partition ranges that still contain unsorted data mixed with already-placed elements. The fix, shown fully in Example 2, is to always swap the pivot into i + 1 before returning:

arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1

Best Practices

• For real projects, prefer Python’s built-in sorted() or list.sort() — they’re implemented in C, use Timsort, and are stable and faster than any hand-written Quicksort.
• Implement Quicksort yourself only for learning, interviews, or specialized cases (e.g. custom in-place memory constraints).
• Use a randomized or median-of-three pivot to avoid the O(n²) worst case on sorted or adversarial input.
• Recurse on the smaller partition first and use a loop for the larger one (tail-call style) to keep worst-case recursion depth at O(log n) instead of O(n).
• Handle duplicate values with a three-way partition (left / middle / right) as shown in the examples — this keeps performance good even when many elements equal the pivot.
• Remember that Quicksort is not stable; if relative order of equal elements matters, use sorted(key=...) instead.
• Add a base case for lists of length 0 or 1 to guarantee recursion terminates.
• Avoid deeply recursive in-place Quicksort on very large untrusted inputs without a pivot strategy — Python’s default recursion limit (around 1000) can be hit by a pathological worst case.

Practice Exercises

• Write a function quicksort_desc(arr) that sorts a list of numbers in descending order using the same divide-and-conquer approach as Example 1.
• Modify the in-place Quicksort from Example 2 to count and print how many total comparisons (arr[j] <= pivot checks) it performs while sorting [5, 2, 9, 1, 5, 6].
• Using the key-based Quicksort from Example 3, sort a list of strings by their length, then, for strings of equal length, discuss (in a comment) why their relative order is not guaranteed to be preserved.

Summary

• Quicksort is a divide-and-conquer algorithm: choose a pivot, partition the list around it, and recursively sort each side.
• Average-case time complexity is O(n log n); worst case is O(n²) when the pivot choice consistently produces unbalanced partitions.
• In-place implementations (like the Lomuto scheme) swap elements within one array and use O(log n) extra space for recursion; functional implementations allocate new lists at each call.
• Quicksort is not stable — equal elements can be reordered.
• Randomized or median-of-three pivot selection protects against worst-case performance on sorted or adversarial input.
• In production Python code, prefer the built-in sorted()/list.sort() over a hand-rolled Quicksort; write your own mainly to understand the algorithm.