Bubble Sort to Timsort: Why Python Ditched O(n )

Python's sort() is too fast to be simple

Run sorted([3,1,2]) in Python and you get [1,2,3] in microseconds. Under the hood, you're not running the bubble sort from your algorithms textbook—you're running Timsort, a hybrid algorithm that combines merge sort and insertion sort, exploits real-world data patterns, and routinely beats $O(n \log n)$ worst-case guarantees in practice. The gap between "sorting 101" and production code is enormous, and most people never see why.

I'm going to show you exactly what happens when you replace the beginner-friendly algorithms with what Python actually uses, and why the performance difference matters even on small datasets.

What bubble sort actually costs

Bubble sort is the first algorithm most of us learn. The idea: repeatedly step through the list, compare adjacent elements, swap if they're out of order. After each pass, the largest unsorted element "bubbles" to its correct position.

Here's the canonical implementation:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:  # Already sorted
            break
    return arr

---

Continue reading the full article on TildAlice