Welcome to Phase 4. Before reaching for sorted()sorted(), it’s worth building the three simplest sorting algorithms by hand at least once. None of them scale past a few thousand elements, but the ideas inside them — comparing neighbors, tracking a running minimum, shifting elements into place — show up again and again once you get to smarter algorithms like Merge Sort and Quick Sort.

What you’ll learn

• Bubble sort — repeatedly swap adjacent out-of-order elements.
• Selection sort — repeatedly pick the minimum of what’s left.
• Insertion sort — build a sorted prefix one element at a time.
• Why all three are $O(n^2)$ on average, and which one is actually useful in practice (hint: it’s not the one most people reach for first).
• Stability — what it means, and which of these three preserve it.

Bubble sort: swap your way to sorted

Bubble sort walks the array left to right, comparing every pair of neighbors. If a pair is out of order, it swaps them. One full pass guarantees the largest remaining value “bubbles” all the way to the end, so each pass can safely ignore one more element at the tail.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:      # nothing moved this pass -- already sorted
            break
    return arr
 
 
nums = [5, 3, 8, 1, 9, 2, 7, 4]
print(bubble_sort(nums))

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:      # nothing moved this pass -- already sorted
            break
    return arr
 
 
nums = [5, 3, 8, 1, 9, 2, 7, 4]
print(bubble_sort(nums))

The swappedswapped flag is the one optimization worth remembering: if a full pass makes zero swaps, the array is already sorted and the algorithm can stop early — that’s what gives bubble sort its best-case $O(n)$ on already-sorted input.

Watch a full pass: the sorted suffix (green) grows by one element every time, and every comparison either swaps (red) or leaves things alone (amber):

Selection sort: pick the minimum, every time

Selection sort flips the logic: instead of bubbling large values to the back, it scans the unsorted remainder for its minimum and swaps that minimum into the front of the unsorted region. After $n - 1$ passes, the whole array is sorted.

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        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
 
 
nums = [5, 3, 8, 1, 9, 2, 7, 4]
print(selection_sort(nums))

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        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
 
 
nums = [5, 3, 8, 1, 9, 2, 7, 4]
print(selection_sort(nums))

Notice selection sort always does the full $\binom{n}{2}$ comparisons, even if the array is already sorted — there’s no early-exit optimization like bubble sort’s swappedswapped flag. Its one redeeming feature is that it does at most $n - 1$ swaps total, which matters if writes are far more expensive than comparisons (e.g. sorting on flash memory).

Insertion sort: grow a sorted prefix

Insertion sort keeps the front of the array as a growing sorted region. For each new element, it shifts everything in the sorted prefix that’s bigger than the new value one slot to the right, then drops the new value into the gap — exactly how most people sort a hand of playing cards.

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]   # shift bigger element right
            j -= 1
        arr[j + 1] = key          # drop key into the gap
    return arr
 
 
nums = [5, 3, 8, 1, 9, 2, 7, 4]
print(insertion_sort(nums))

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]   # shift bigger element right
            j -= 1
        arr[j + 1] = key          # drop key into the gap
    return arr
 
 
nums = [5, 3, 8, 1, 9, 2, 7, 4]
print(insertion_sort(nums))

Time and space complexity

All three sort in place ($O(1)$ extra space) and none of them beat $O(n^2)$ on average — that’s exactly the gap Merge Sort and Quick Sort close, next.

LeetCode problem set

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 905 — Sort Array By Parity · Easy

Problem. Move all the even integers before all the odd integers. Any such arrangement is accepted.

Constraints. 1 <= len(nums) <= 50001 <= len(nums) <= 5000, 0 <= nums[i] <= 50000 <= nums[i] <= 5000.

Examples. [3,1,2,4][3,1,2,4] gives [2,4,3,1][2,4,3,1] — and [4,2,3,1][4,2,3,1] is equally valid

LC 75 — Sort Colors · Medium

Problem. Sort an array containing only 00, 11 and 22 in place, so that equal values are adjacent and in the order 0, 1, 20, 1, 2. You may not use a library sort, and should do it in one pass.

Constraints. 1 <= len(nums) <= 3001 <= len(nums) <= 300, values are 00, 11 or 22.

Examples. [2,0,2,1,1,0][2,0,2,1,1,0] gives [0,0,1,1,2,2][0,0,1,1,2,2] · [2,0,1][2,0,1] gives [0,1,2][0,1,2]

LC 147 — Insertion Sort List · Medium

Problem. Sort a linked list using insertion sort and return the sorted head.

Constraints. 1 <= number of nodes <= 50001 <= number of nodes <= 5000, -5000 <= Node.val <= 5000-5000 <= Node.val <= 5000.

Examples. [4,2,1,3][4,2,1,3] gives [1,2,3,4][1,2,3,4] · [-1,5,3,4,0][-1,5,3,4,0] gives [-1,0,3,4,5][-1,0,3,4,5]

Recap

• Bubble sort swaps adjacent out-of-order elements; a swappedswapped flag gives it a best case of $O(n)$ on sorted input.
• Selection sort always scans for the true minimum and does at most $n - 1$ swaps total, but it’s not stable.
• Insertion sort grows a sorted prefix by shifting; it’s stable and genuinely fast ($O(n)$) on nearly-sorted data.
• All three are $O(n^2)$ on average and worst case, with $O(1)$ extra space.

Next: Merge Sort — the first algorithm in this course to break past $O(n^2)$, using divide and conquer to guarantee $O(n \log n)$ every time.