Lesson 25 / 42

Bubble, Selection, Insertion Sort

The three O(n^2) sorts — simple, in place, good for tiny or nearly-sorted inputs.

How each one moves data

Bubble: repeatedly swap adjacent out-of-order pairs; large values "bubble" to the end. Selection: each pass finds the minimum of the rest and puts it next. Insertion: take the next element and slide it left into its sorted place.

Insertion sort

The best of the three in practice: O(n) on nearly-sorted data and stable.

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]   # shift right
            j -= 1
        a[j + 1] = key        # drop key in place
    return a

Complexity & stability

All three: O(n^2) average/worst, O(1) space. Insertion is O(n) best case. Bubble and insertion are stable (keep equal elements' order); selection is not. Selection does the fewest swaps (O(n)).

Reality check

In production you call the library sort. These matter for interviews and as the base case inside faster sorts (e.g. Timsort uses insertion sort on small runs).