Basic sorting — how sorting actually works

Before reaching for sorted() and moving on, walking through one sorting algorithm by hand is what makes "why is this O(n^2)" concrete instead of memorized.

Beginner

4 min read

The problem, stated precisely

Given a list of values, produce a new ordering of the same values from smallest to largest (or largest to smallest). Python's built-in sorted() does this in one call — sorted([3, 1, 2]) gives [1, 2, 3] — and for real code, that's almost always the right tool. This lesson isn't about replacing it; it's about seeing what a sorting algorithm actually does step by step, which is what makes complexity numbers like O(n^2) and O(n log n) concrete rather than abstract labels.

Bubble sort: the simplest one to trace by hand

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]   # swap
    return arr

The idea: repeatedly walk through the list, comparing each pair of neighbors, and swap them if they're out of order. One full pass through the list "bubbles" the largest remaining value all the way to its correct position at the end — like a bubble rising to the top. Repeating this pass, one fewer element each time (since the end is already correctly sorted), eventually sorts the whole list.

Why bubble sort is O(n^2) — visible directly in the code

The outer loop runs roughly n times; the inner loop, for each outer pass, compares roughly n pairs. That's a loop nested inside a loop over the same data — the exact shape the Big-O intuition lesson calls out as the visual signature of O(n^2). For a list of 10 items, that's roughly 100 comparisons; for 10,000 items, roughly 100,000,000 — this is precisely why bubble sort, despite being the easiest to understand, is never used on real, large data.

Selection sort: a different strategy, same complexity

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

Instead of repeatedly swapping neighbors, selection sort repeatedly finds the smallest remaining value and moves it directly into its correct position — for each position from left to right, scan the rest of the list for the minimum, then swap it into place. It's a genuinely different strategy from bubble sort, but the nested-loop shape is identical, so it's O(n^2) too. Seeing two different-looking algorithms both reduce to "nested loop over the same data" is the point: the specific strategy mattered less than the underlying shape.

Why `sorted()` doesn't use either of these

Python's built-in sorted() uses Timsort, a hybrid, highly-optimized algorithm that runs in O(n log n) in the worst case — meaningfully faster than O(n^2) for any real-sized list, and it also takes advantage of already-partially-sorted data (common in real-world input) to go even faster. The general pattern — a well-chosen comparison-based sort achieves O(n log n), not O(n^2) — is what the hierarchy in the Big-O lesson's table refers to under "efficient comparison-based sorting"; the mechanism behind that jump (splitting the problem in half repeatedly, the way merge sort works) is worth returning to once recursion and divide-and-conquer thinking feel comfortable.

The actual takeaway

You will essentially never hand-write a sorting algorithm in real production code — sorted() (or .sort()) is correct, fast, and well-tested. The value of walking through bubble sort and selection sort by hand is purely about building the instinct for reading a nested loop and immediately recognizing "this is O(n^2)," and for feeling — not just knowing abstractly — why an O(n log n) algorithm scales so much better once real-sized data is involved.