Sorting7 min read

Basic Sorts

Sorting a hand of cards — three ways, one speed
bubble sort:\(O(n^2)\) — swap neighborsselection sort:\(O(n^2)\) — find minimuminsertion sort:\(O(n)\) best · \(O(n^2)\) worststable:Bubble ✓ · Insertion ✓ · Selection ✗

Imagine you've just been dealt a hand of playing cards and you want to sort them. There are three natural, human-style approaches:

Option A: Scan left to right, swap any two neighbors that are out of order. Repeat until the hand is sorted. That's bubble sort.

Option B: Find the lowest card in your unsorted cards, pull it out, set it aside in sorted order. Repeat. That's selection sort.

Option C: Pick up cards one at a time and slide each new card into its correct position among the cards you're already holding. That's insertion sort.

All three are \(O(n^2)\) in the worst case. But they have very different personalities.

Bubble Sort — Neighbors Swap Their Way Up

Bubble sort does passes through the array, swapping adjacent pairs that are out of order. After each pass, the largest unsorted element has "bubbled" to its correct spot at the end. With an early-exit optimization (stop if a pass makes no swaps), it runs in \(O(n)\) on already-sorted input. In the worst case (reverse-sorted), it makes \(O(n^2)\) swaps. It's stable — equal elements never swap past each other.

Selection Sort — Always Find the Minimum

For each position i, selection sort scans the remaining unsorted portion to find the minimum element, then swaps it into position i. It always makes exactly n(n−1)/2 comparisons regardless of input — no early exit possible. It performs at most n−1 swaps, which is useful when writes are expensive. It's not stable: swapping the minimum into place can skip over equal elements, changing their relative order.

Insertion Sort — Slide Into Place

Insertion sort builds a sorted subarray from left to right. For each new element, it shifts elements in the sorted portion rightward until it finds the right slot to insert. On nearly-sorted input, very little shifting is needed: \(O(n)\) total. On reverse-sorted input, every element shifts past all previous ones: \(O(n^2)\). It's stable and in-place.

Insertion sort is the algorithm of choice for small arrays (n ≤ 16–32). Production sort implementations like Python's Timsort and C++'s Introsort fall back to insertion sort for small sub-arrays because its tiny constant and cache-friendly access pattern make it fastest there. For larger arrays, algorithms like merge sort and quicksort take over with their \(O(n \log n)\) performance.

Note: Insertion sort is the card-sorting champion for small hands. If your array is nearly sorted or tiny, insertion sort will beat merge sort and quicksort in practice — not because of Big-O, but because of cache friendliness and low overhead.

All Three Sorts — Side by Side

def bubble_sort(arr):
    a = arr[:]
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:
            break
    return a


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


def insertion_sort(arr):
    a = arr[:]
    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]
            j -= 1
        a[j + 1] = key
    return a


data = [5, 3, 8, 1, 9, 2]
print("Bubble:   ", bubble_sort(data))
print("Selection:", selection_sort(data))
print("Insertion:", insertion_sort(data))
Output
Bubble:    [1, 2, 3, 5, 8, 9]
Selection: [1, 2, 3, 5, 8, 9]
Insertion: [1, 2, 3, 5, 8, 9]

Complexity

🫧 Bubble Sort — best caseWith early-exit: one pass, no swaps found
Linear (already sorted)\(O(n)\)
🫧 Bubble Sort — worst caseReverse-sorted input — maximum swaps needed
Quadratic\(O(n^2)\)
🏆 Selection Sort — all casesAlways n(n−1)/2 comparisons — no early exit. But only ≤ n swaps.
Quadratic always\(O(n^2)\)
🃏 Insertion Sort — best caseAlready-sorted input needs \(O(1)\) shifts per element
Linear (nearly sorted)\(O(n)\)
🃏 Insertion Sort — worst caseEvery element shifts past all prior elements
Quadratic (reverse sorted)\(O(n^2)\)

Quick check

You're sorting 15 nearly-sorted integers. Which algorithm wins in practice?

Continue reading

Merge Sort
Split, sort each half, merge — guaranteed \(O(n \log n)\) every time
→
Quick Sort
Pick a pivot, split the crowd — everyone shorter left, taller right
→