Sorting Algorithms in Python

For real code, just use the built-in: sorted(data) returns a new list and data.sort() sorts in place. Both use Tim Sort, are stable, and run in O(n log n). Use the key parameter for custom orderings, e.g. sorted(users, key=lambda u: u.age).

def quick_sort(a):
    if len(a) <= 1:
        return a
    pivot = a[len(a) // 2]
    left = [x for x in a if x < pivot]
    mid = [x for x in a if x == pivot]
    right = [x for x in a if x > pivot]
    return quick_sort(left) + mid + quick_sort(right)

This concise version is readable but not in-place; see the Quick Sort guide for the in-place partition scheme.

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

Insertion Sort is great for small lists. For larger data use Merge or Quick Sort, or simply the built-in.

Both list.sort() and the built-in sorted() use Tim Sort, a hybrid of Merge Sort and Insertion Sort written for CPython by Tim Peters in 2002 and shipped from CPython 2.3 onwards. It was designed for Python specifically, and it turned out well enough that Java, Swift, Rust and Android later adopted it or a close variant.

The core idea is that real-world data is rarely random. Tim Sort exploits that:

• It scans the list for runs — stretches that are already ascending or strictly descending. Descending runs are simply reversed in place.
• Runs shorter than a computed minimum length (typically 32 to 64) are extended using binary Insertion Sort, which is very fast at that size.
• The runs are then merged in a carefully chosen order, using a temporary buffer and a technique called galloping to skip over long stretches that need no interleaving.

The consequence is that Python's sort is adaptive: O(n log n) worst case, but genuinely O(n) on data that is already sorted or nearly sorted. Since a great deal of real data is nearly sorted, this shows up as a real speed-up rather than a theoretical one.

One accuracy note worth knowing: CPython 3.11 replaced Tim Sort's original run-merging policy with powersort, which chooses a provably better merge order. It is still Tim Sort in every respect that matters to you — same adaptivity, same stability, same interface — but if you compare CPython's source across versions, that is the difference you will find.