Bubble, Selection & Insertion Sort

These three sorts share the same O(n²) time complexity and the same "compare neighbors, fix things one step at a time" spirit, but they get there in different ways. None of them is what you'd actually call in production Python — sorted() and list.sort() are always faster — but each one teaches a different idea that reappears constantly in DSA: repeated passes, tracking a running minimum, and building up a sorted region incrementally.

Bubble Sort

Repeatedly walk through the list comparing each pair of neighbors, swapping them if they're out of order. Each full pass "bubbles" the largest remaining unsorted value up to its correct position at the end. An swapped flag lets it stop early once a full pass makes no swaps at all — a sign the list is already sorted.

def bubble_sort(items):
    n = len(items)
    for i in range(n):
        swapped = False
        # after i passes, the last i elements are already in final position
        for j in range(0, n - i - 1):
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
                swapped = True
        if not swapped:
            break              # no swaps this pass -- already sorted, stop early
    return items


print(bubble_sort([5, 2, 9, 1, 5]))

Trace on [5, 2, 9, 1, 5]: pass 1 compares (5,2)→swap→[2,5,9,1,5], (5,9) no swap, (9,1)→swap→[2,5,1,9,5], (9,5)→swap→[2,5,1,5,9] -- 9 has bubbled to the end. Pass 2 on the remaining [2,5,1,5]: (2,5) no swap, (5,1)→swap→[2,1,5,5], (5,5) no swap -- 5 settles into place. Pass 3: (2,1)→swap→[1,2,5,5] -- fully sorted, and pass 4 makes no swaps, so the early-exit flag stops the function there.

Time complexity: O(n²) worst and average case (n passes, each up to n comparisons) but O(n) best case on an already-sorted list, thanks to the early-exit flag. Space complexity: O(1) — sorting happens in place with only a couple of index variables.

Selection Sort

For each position, scan the entire remaining unsorted portion to find its minimum value, then swap that minimum into place. Unlike bubble sort, selection sort always does exactly one swap per outer iteration — it just does more comparisons finding which element to swap.

def selection_sort(items):
    n = len(items)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if items[j] < items[min_index]:
                min_index = j              # track the smallest value seen so far
        items[i], items[min_index] = items[min_index], items[i]
    return items


print(selection_sort([5, 2, 9, 1, 5]))

Trace on [5, 2, 9, 1, 5]: i=0, scan indices 1..4 for the minimum -- finds 1 at index 3, swap with index 0 → [1,2,9,5,5]. i=1, scan indices 2..4 -- minimum is 2 already at index 1... wait, minimum of [9,5,5] is 5 at index 3, swap with index 1 → [1,5,9,2,5]. Continuing this way, each iteration guarantees the sorted prefix grows by exactly one correctly-placed element.

Time complexity: O(n²) in every case — best, average, and worst are identical, since the inner scan for the minimum always examines every remaining element regardless of input order. Space complexity: O(1) — in-place with one tracked minimum index.

Insertion Sort

Build up a sorted region at the front of the list one element at a time. For each new element, shift it leftward past every already-sorted element that's bigger than it, until it lands in its correct spot — the same motion you use sorting playing cards in your hand.

def insertion_sort(items):
    for i in range(1, len(items)):
        key = items[i]                     # the element being inserted into the sorted prefix
        j = i - 1
        while j >= 0 and items[j] > key:
            items[j + 1] = items[j]       # shift bigger element one slot right
            j -= 1
        items[j + 1] = key             # drop key into the gap it opened
    return items


print(insertion_sort([5, 2, 9, 1, 5]))

Trace on [5, 2, 9, 1, 5]: i=1, key=2, shift 5 right → [2,5,9,1,5]. i=2, key=9, nothing bigger to its left, stays → [2,5,9,1,5]. i=3, key=1, shift 9, 5, 2 all right → [1,2,5,9,5]. i=4, key=5, shift 9 right, stop at 5 (not bigger) → [1,2,5,5,9] -- sorted.

Time complexity: O(n²) worst/average case (each new element can shift past all previously sorted ones) but O(n) best case on an already-sorted list, since the inner while loop condition fails immediately every time. Space complexity: O(1) — in-place with one key value and one index held at a time.

Why Teach O(n²) Sorts At All?

Nobody uses these in real code, but they're taught because they're the simplest possible vehicle for ideas you'll reuse constantly: repeated linear passes, tracking a running best value, and maintaining a growing sorted invariant. Insertion sort specifically also has a genuine practical niche — it's very fast on nearly-sorted data and on tiny lists, which is exactly why real sorting libraries (including Python's own) fall back to it for small sub-arrays, as you'll see below.

Stability Compared

A sort is stable if two elements that compare equal keep their original relative order. This matters whenever you sort by one key but care about a previous ordering by another key (e.g. sort students by grade, but names that already came alphabetically should stay that way within each grade).

Algorithm	Stable?	Why
Bubble Sort	Yes	Only swaps adjacent elements when strictly out of order, so equal elements are never swapped past each other.
Selection Sort	No (typically)	Swapping the minimum into position can jump it past equal elements sitting between its old and new position, disturbing their relative order.
Insertion Sort	Yes	An element only shifts past values strictly greater than it, so equal elements are never reordered relative to each other.

Python's Real Sort: Timsort

sorted() and list.sort() don't use any of the three algorithms above by themselves — they use Timsort, a hybrid designed by Tim Peters specifically for Python. Timsort splits the data into small runs, sorts each run with insertion sort (genuinely fast for small n, as noted above), then merges the runs together using the same merge idea you'll meet in the next lesson on merge sort. It's stable, adapts well to partially-sorted real-world data, and guarantees O(n log n) worst case.

numbers = [5, 2, 9, 1, 5]

print(sorted(numbers))   # [1, 2, 5, 5, 9] -- returns a new sorted list, Timsort under the hood
numbers.sort()          # sorts numbers in place, also Timsort
print(numbers)

Time complexity: O(n log n) worst case, O(n) best case on already-sorted or nearly-sorted data — Timsort detects existing runs and merges them with far fewer comparisons than a from-scratch sort would need. Space complexity: O(n) — merging runs needs a temporary buffer, unlike the in-place O(1) sorts above.