Sorting Algorithms I

Bubble Sort

Repeatedly walk the list, swapping any adjacent pair that's out of order. Each full pass "bubbles" the largest remaining value to its final position at the end, so after k passes, the last k elements are guaranteed sorted and never touched again.

def bubble_sort(items: list[int]) -> list[int]:
    n = len(items)
    for i in range(n):
        swapped = False
        for j in range(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   # nothing moved this pass, the list is already sorted
    return items

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

[1, 2, 3, 5, 8, 9]

Each pass walks the list once, and by the end of it the largest value still in play has "bubbled" to its final slot. Watch that sorted tail (green) grow from the right, one element per pass:

Selection Sort

Find the smallest remaining value and swap it into its correct position, then repeat for the rest of the list. Where bubble sort does many small swaps, selection sort does at most one swap per pass, at the cost of always scanning the entire unsorted remainder to find that minimum.

def selection_sort(items: list[int]) -> list[int]:
    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
        items[i], items[min_index] = items[min_index], items[i]
    return items

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

[1, 2, 3, 5, 8, 9]

Where bubble sort grew a sorted region from the right, selection sort grows one from the left. Each pass finds the smallest remaining value and swaps it into the next position, so the green prefix extends by one every time:

Because it always scans to the end looking for the minimum, selection sort can't detect an already-sorted list early the way bubble sort can, it's O(n²) in the best, average, and worst case alike.

Insertion Sort

Build the sorted portion one element at a time, growing from the left. Each new element gets shifted backward, exactly Lesson 2's O(n) front-insertion cost, until it lands in its correct spot among everything already sorted.

def insertion_sort(items: list[int]) -> list[int]:
    for i in range(1, len(items)):
        key = items[i]
        j = i - 1
        while j >= 0 and items[j] > key:
            items[j + 1] = items[j]   # shift larger elements one slot right
            j -= 1
        items[j + 1] = key            # drop key into the gap it opened up
    return items

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

[1, 2, 3, 5, 8, 9]

Insertion sort also builds a sorted prefix from the left, but by a different move: it takes the next element and slides it back into its correct spot among the already-sorted ones. When an element is already in order (like 8 and 9 below), it barely moves:

Merge Sort

All three algorithms above are O(n²) because they only ever compare and shift elements one at a time. Merge sort takes a completely different approach: split the list in half recursively (Lesson 5's call stack again) until each piece has one element, trivially sorted, then merge sorted pieces back together two at a time.

def merge_sort(items: list[int]) -> list[int]:
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])
    return merge(left, right)

def merge(left: list[int], right: list[int]) -> list[int]:
    result: list[int] = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:       # "<=", not "<": keeps equal keys stable
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge_sort([5, 3, 8, 1]))

[1, 3, 5, 8]

The splitting is the easy half; the real work is the merge. Here is the final merge from the figure above, combining the two sorted halves [3, 5] and [1, 8]. Each step compares the two front elements and takes the smaller one, so the result comes out sorted:

Figure 5: One full merge does a single linear pass over both halves, which is the O(n) work done at each of the log n levels.

The split happens log₂(n) times, and merging all the pieces back together at each level costs O(n) total, exactly the same O(n log n) shape as Lesson 1's example of linearithmic growth.

Complexity at a Glance

Merge sort's guaranteed O(n log n) comes at a real cost: unlike the other three, it needs O(n) extra space to hold the merged results, it can't sort purely by swapping within the original list.

Stability: The Property Big-O Doesn't Capture

A sort is stable if elements that compare equal keep their original relative order. This matters whenever you're sorting by one field but care about another, sorting orders by date should never scramble same-day orders that were already sorted by customer name.

Selection sort's swap-based approach breaks this: swapping the minimum into place can leapfrog it past an equal element that was already correctly positioned.

# Sort by score only; letter is just there to reveal original order
data = [(3, "a"), (1, "b"), (3, "c"), (2, "d"), (1, "e"), (3, "f")]

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

print(selection_sort_by_score(data.copy()))

[(1, 'b'), (1, 'e'), (2, 'd'), (3, 'c'), (3, 'a'), (3, 'f')]

Notice the two entries scoring 3, "a" and "c", ended up swapped from their original order, "c" now comes before "a". Bubble sort, insertion sort, and merge sort (thanks to that <= in merge) are all stable; selection sort is the one exception among the four in this lesson.