Bubble Sort, Selection Sort, and Insertion Sort Explained

Bubble sort, selection sort, and insertion sort are usually the first three sorting algorithms anyone learns — not because they're efficient (they're all O(n²) on average), but because each one teaches a distinct, intuitive way of thinking about "putting things in order" that shows up again later in faster algorithms.

Bubble Sort: Repeatedly Swap Neighbors

Bubble sort repeatedly walks through the list, comparing each pair of adjacent elements and swapping them if they're out of order. Each full pass "bubbles" the largest remaining unsorted element up to its correct position at the end — after n passes, the whole list is sorted.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(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, stop early
            break
    return arr

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

Output:

[1, 2, 5, 5, 6, 9]

The swapped flag is a nice touch: if a full pass makes zero swaps, the list is already sorted, and bubble sort can exit early — turning its best case into O(n) on already-sorted data.

Selection Sort: Repeatedly Pick the Minimum

Selection sort takes the opposite approach: instead of swapping neighbors repeatedly, it scans the unsorted portion of the list to find the smallest remaining element, then swaps it into its correct position — one swap per pass, guaranteed.

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

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

Output:

[1, 2, 5, 5, 6, 9]

Selection sort always makes exactly n−1 swaps regardless of the input, which makes it mildly attractive when swaps are expensive (e.g. writing to flash memory) — but it never gets the early-exit speedup bubble sort can, since it always scans the full remaining unsorted section every pass.

Insertion Sort: Build Up a Sorted Prefix

Insertion sort grows a sorted section at the front of the list one element at a time — much like sorting a hand of playing cards. It takes the next unsorted element and shifts it backward into its correct position among the already-sorted elements before it.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

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

Output:

[1, 2, 5, 5, 6, 9]

When Are These Actually a Reasonable Choice?

All three run in O(n²) on average, far slower than merge sort or quick sort's O(n log n) on large inputs — but insertion sort in particular is genuinely useful on very small arrays or nearly-sorted data, where its best case drops to O(n). That's not a theoretical footnote: many real-world "fast" sorting algorithms, including Python's Timsort, switch to insertion sort under the hood once a sublist shrinks below a small size threshold, because the overhead of a fancier algorithm isn't worth it at that scale. See the sorting algorithms overview for how all the major algorithms compare side by side.