Sorting Algorithms in Python

Sorting is everywhere — leaderboards, search results, reports — and sorting algorithms are the classic way to learn algorithmic thinking and complexity analysis. In real Python code you will almost always use the built-in sorted() and list.sort(), which use the highly optimised Timsort. Knowing how the classic algorithms work is still essential for interviews and for understanding performance.

This lesson implements bubble, selection, insertion, merge, quick and heap sort, explains Timsort, and compares their time complexity, stability and memory use.

Simple O(n²) Sorts

Bubble sort repeatedly swaps adjacent out-of-order items so the largest "bubbles" to the end; with an early-exit flag it is O(n) on already-sorted data. Selection sort repeatedly selects the smallest remaining item and puts it in place — always O(n²), but few swaps. Insertion sort builds a sorted prefix by inserting each new item into place — fast for small or nearly sorted lists, which is why Timsort uses it internally.

Efficient O(n log n) Sorts

Merge sort splits the list in half, sorts each half recursively and merges them — always O(n log n), stable, but needs O(n) extra memory. Quick sort partitions around a pivot and sorts each side — O(n log n) on average, O(n²) in the worst case (mitigated by random pivots). Heap sort builds a heap and extracts the minimum repeatedly — O(n log n) with O(1) extra memory, but not stable.

Timsort: Python's Built-in Sort

Timsort (created by Tim Peters for Python) finds already-ordered "runs" in the data, extends short runs with insertion sort, and merges runs efficiently. It is O(n log n) in the worst case, O(n) on sorted data, and stable — equal items keep their original order, which lets you sort by several keys in successive passes.

Comparison

Summary of the algorithms:

Bubble — best O(n), average/worst O(n²), stable, in place.
Selection — O(n²) always, not stable, in place.
Insertion — best O(n), worst O(n²), stable, in place.
Merge — O(n log n) always, stable, O(n) extra memory.
Quick — average O(n log n), worst O(n²), not stable, in place.
Heap — O(n log n), not stable, in place.
Timsort — best O(n), worst O(n log n), stable (Python's sorted/sort).

Examples

Bubble, selection and insertion sort

Python

def bubble_sort(items):
    a = items[:]
    for end in range(len(a) - 1, 0, -1):
        swapped = False
        for i in range(end):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                swapped = True
        if not swapped:
            break
    return a

def selection_sort(items):
    a = items[:]
    for i in range(len(a)):
        smallest = min(range(i, len(a)), key=a.__getitem__)
        a[i], a[smallest] = a[smallest], a[i]
    return a

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

data = [64, 25, 12, 22, 11, 90, 5]
print(bubble_sort(data))
print(selection_sort(data))
print(insertion_sort(data))

Output

[5, 11, 12, 22, 25, 64, 90]
[5, 11, 12, 22, 25, 64, 90]
[5, 11, 12, 22, 25, 64, 90]

Merge sort, quick sort and heap sort

Python

import heapq
import random

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    merged, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    return merged + left[i:] + right[j:]

def quick_sort(a):
    if len(a) <= 1:
        return a
    pivot = random.choice(a)
    return (quick_sort([x for x in a if x < pivot])
            + [x for x in a if x == pivot]
            + quick_sort([x for x in a if x > pivot]))

def heap_sort(a):
    heap = a[:]
    heapq.heapify(heap)
    return [heapq.heappop(heap) for _ in range(len(heap))]

data = [38, 27, 43, 3, 9, 82, 10, 27]
print(merge_sort(data))
print(quick_sort(data))
print(heap_sort(data))

Output

[3, 9, 10, 27, 27, 38, 43, 82]
[3, 9, 10, 27, 27, 38, 43, 82]
[3, 9, 10, 27, 27, 38, 43, 82]

Timsort in practice: stability and multi-key sorting

Python

students = [("Asha", "B", 88), ("Ravi", "A", 72), ("Meera", "B", 95), ("Kiran", "A", 72)]

# Stable sorting: sort by the secondary key first, then by the primary key
by_name = sorted(students, key=lambda s: s[0])
by_section_then_name = sorted(by_name, key=lambda s: s[1])
print([s[0] for s in by_section_then_name])

# Or in one pass with a tuple key: highest marks first, then name
ranked = sorted(students, key=lambda s: (-s[2], s[0]))
print([(s[0], s[2]) for s in ranked])

Output

['Kiran', 'Ravi', 'Asha', 'Meera']
[('Meera', 95), ('Asha', 88), ('Kiran', 72), ('Ravi', 72)]

Comparing speed on the same data

Python

import random
import time

random.seed(1)
data = [random.randint(0, 10_000) for _ in range(3_000)]

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

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]

timings = {}
for name, fn in [("insertion O(n^2)", insertion_sort), ("merge O(n log n)", merge_sort), ("built-in Timsort", sorted)]:
    start = time.perf_counter()
    result = fn(data)
    timings[name] = time.perf_counter() - start
    assert result == sorted(data)

fastest = min(timings, key=timings.get)
print("all results correct; fastest:", fastest)
print("insertion slower than merge:", timings["insertion O(n^2)"] > timings["merge O(n log n)"])

Output

all results correct; fastest: built-in Timsort
insertion slower than merge: True

Common Mistakes

Implementing your own sort in production code instead of using sorted()/list.sort().
Forgetting that list.sort() sorts in place and returns None.
Using the first element as quick sort's pivot on already-sorted data, causing O(n²).
Assuming all sorts are stable — selection, quick and heap sort are not.

Key Points to Remember

Bubble, selection and insertion sort are O(n²); insertion is fast on nearly sorted data.
Merge, quick and heap sort are O(n log n) (quick sort on average).
Python uses Timsort: stable, O(n log n) worst case, O(n) on sorted data.
Stability enables multi-key sorting; tuple keys do it in one pass.

Practice the examples

Change an input, predict the result, then compare it with the output. Explain why the result changes.

Try Bubble, selection and insertion sort in Webnest Codelab Try Merge sort, quick sort and heap sort in Webnest Codelab Try Timsort in practice: stability and multi-key sorting in Webnest Codelab Try Comparing speed on the same data in Webnest Codelab