Sorting I: Bubble, Insertion, Selection

Three hand-written comparison sorts that rearrange a list in place, all O(n²) time and O(1) space.

Core terms

• Sort: rearrange into order, usually ascending (smallest first).
• Index: position, counted from 0.
• Swap: a[i], a[j] = a[j], a[i] (right side evaluated first, so no value is lost).
• Comparison: e.g. a[i] > a[j].
• Pass: one full sweep through the list.
• Comparison sort: only ever compares two elements and maybe swaps.
• In place: rearranges the original list, O(1) extra space.

Bubble sort

• Sweep neighbors; swap if left > right. Largest bubbles to the far right each pass.
• Inner loop shrinks: range(n - 1 - i) (last i elements already settled).
• Early-exit: if a pass makes zero swaps, stop. Makes it O(n) on already-sorted input.
• Many swaps per pass. Stable.

Selection sort

• Scan the unsorted part for the minimum, then one swap to put it at the front.
• At most one swap per pass (all the looking, then one exchange) → fewest swaps.
• Always O(n²), even if already sorted. Not stable (a long-distance swap can jump over an equal element).

Insertion sort

• Grow a sorted left region; slide each new element leftward past larger elements into its gap.
• Save key = a[i] before shifting (shifting overwrites a[i]).
• while j >= 0 and a[j] > key: shift right; drop key at a[j + 1].
• Best case O(n) on sorted / nearly-sorted input (while loop barely runs). Stable.
• Wins on small (<10-20) or nearly-sorted lists; libraries switch to it for small sub-lists.

Compare

Why O(n²) / O(1)

• Reverse-sorted worst case: inner loop shifts 1 + 2 + ... + (n-1) = n(n-1)/2 → dominant n²/2 → O(n²).
• Double the input, work roughly quadruples.
• Space: a fixed handful of vars (i, j, key, min_index) regardless of n → O(1).

Gotchas

• Off-by-one: bubble inner loop must stop at n - 2; reading a[j+1] past the end raises IndexError.
• Bad two-step swap (a[i] = a[j]; a[j] = a[i]) copies one value into both slots.
• Forgetting to save key before shifting gives wrong results.
• Selection sort is not stable; do not use it when order among equal items matters.
• These sorts mutate the caller’s list; pass original[:] (shallow copy) to keep the original.