Simple sorts: bubble, selection and insertion

Why learn sorts you will not use?

In real code you call sorted() and move on. But interviewers ask about simple sorts because they teach the words used for every sort (pass, swap, in place, stable), they are easy to trace by hand, and insertion sort is genuinely used inside fast library sorts for small pieces. Sorting means putting items in order, here non-decreasing order: each item is less than or equal to the next.

Bubble sort

Walk through the list and compare each pair of neighbours; if the left one is bigger, swap them. After one pass the largest item has "bubbled" to the end, so the next pass can stop one place earlier. With an early exit, if a whole pass makes no swaps, the list is already sorted and you stop.

[5, 1, 4, 2]
pass 1: swap 5,1 → [1, 5, 4, 2]; swap 5,4 → [1, 4, 5, 2]; swap 5,2 → [1, 4, 2, 5]
pass 2: 1,4 fine; swap 4,2 → [1, 2, 4, 5]          (5 is already in place)
pass 3: 1,2 fine → no swaps, so stop early

Selection sort

Find the smallest item in the unsorted part and swap it to the front of that part; then the sorted part grows by one. It always does about n²/2 comparisons, even on sorted input, but at most n − 1 swaps, which matters only when writing to memory is very costly.

[29, 10, 14, 37, 13]
round 1: smallest is 10 → swap with 29 → [10, 29, 14, 37, 13]
round 2: smallest of the rest is 13 → swap with 29 → [10, 13, 14, 37, 29]
round 3: 14 is already in place
round 4: smallest of [37, 29] is 29 → swap → [10, 13, 14, 29, 37]

Insertion sort

This is how most people sort a hand of playing cards. The left part is always sorted. Take the next item (the key), shift every bigger item in the sorted part one place right, and drop the key into the gap.

def insertion_sort(nums):
    a = list(nums)                 # work on a copy
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:   # > (not >=) keeps equal items in order
            a[j + 1] = a[j]            # shift right
            j -= 1
        a[j + 1] = key
    return a

print(insertion_sort([5, 2, 4, 1]))   # Output: [1, 2, 4, 5]

Insertion sort does one shift per inversion (a pair in the wrong order, as in Module 5). A nearly sorted list has few inversions, so insertion sort runs in about O(n + inversions), close to O(n). That is why library sorts use it for short or almost-sorted runs.

Costs at a glance

In place means the sort rearranges the list itself, using only O(1) extra memory. All three are in place (the code above copies the input first only so the caller's list does not change).

Stability

A sort is stable if items with EQUAL keys keep their original relative order. Suppose a class list is in alphabetical order and you sort it by marks. With a stable sort, students who scored the same marks stay in alphabetical order, so you get "sorted by marks, then by name" for free.

students = [("Asha", 82), ("Kiran", 75), ("Meena", 82), ("Ravi", 75)]   # by name
print(sorted(students, key=lambda s: s[1], reverse=True))
# Output: [('Asha', 82), ('Meena', 82), ('Kiran', 75), ('Ravi', 75)]

Selection sort is not stable because its long-distance swap can jump an item over an equal one. Sorting [(2, "a"), (2, "b"), (1, "c")] by the number, round 1 swaps (1, "c") with (2, "a"), giving [(1, "c"), (2, "b"), (2, "a")]: "b" is now before "a".

Common mistakes

• Using >= instead of > when comparing in bubble or insertion sort. It still sorts, but equal items get swapped, so the sort is no longer stable. Fix: move an item only when it is strictly bigger.
• Running bubble sort's inner loop to the end every pass. Fix: after pass k the last k items are final, so stop earlier.
• Forgetting the early exit, so a sorted list still costs O(n²). Fix: track whether a pass swapped anything.
• Off-by-one in insertion sort: losing the key by shifting before saving it. Fix: store key = a[i] first, and write it at a[j + 1] at the end.
• Calling these sorts in production code. Fix: use the built-in sort; learn these for interviews and for small or nearly sorted data.