Elementary Sorts

Welcome to Phase 4. Before reaching for 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.

The cue

Nobody asks you to bubble sort. These algorithms are on the page for three reasons that do come up.

You are looking at an elementary sort when…

• The input is nearly sorted or small. Insertion sort is $O(n + \text{inversions})$ — genuinely the best choice below ~16 elements, which is why Timsort and every production quicksort fall back to it.
• The data arrives incrementally and must stay sorted. Insertion sort is the only one of the three that is online: it never needs to see the whole input.
• Swaps are expensive and comparisons are cheap — writing to flash, moving physical objects. Selection sort does at most n - 1 swaps, the fewest of any comparison sort.
• The problem is really about counting inversions or adjacent swaps — “minimum adjacent swaps to sort” is exactly bubble sort’s swap count. LC 1370-style, and 2340.
• An interviewer wants to see whether you can reason about a nested loop’s exact cost, not just quote $O(n^2)$.

When it is the wrong tool. Any large unsorted array — use list.sort(). And note that "$O(n^2)$" hides three genuinely different algorithms: their comparison counts, swap counts and adaptivity all differ, and the differences are what the questions are about.

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.

bubble_sort.py

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 swapped 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):

sketch Bubble sort: one comparison at a time p5.js Pause Restart

Adjacent bars are compared (amber). If the left bar is bigger, they swap (red). Once a pass finishes, the largest remaining value has bubbled to the end -- that slot turns green and is never touched again.

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.

selection_sort.py

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 swapped 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).

Selection sort is not stable

Swapping the minimum into place can jump it past equal elements that were sitting in between, changing their relative order. For example, sorting [3a, 3b, 1] (two equal 3’s, tagged for tracking) swaps the 1 with the first 3a, leaving [1, 3b, 3a] — the two 3’s swapped relative order. Bubble sort and insertion sort never do this, because they only ever swap adjacent elements.

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.

insertion_sort.py

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))

When insertion sort actually wins

If the array is already nearly sorted, the while loop barely runs — each element only shifts past a handful of out-of-place neighbors, giving a best case of $O(n)$. That’s exactly why real-world hybrid sorts (Python’s Timsort included) fall back to insertion sort for small or nearly-sorted runs instead of paying the overhead of a fancier algorithm.

Dry run

The three algorithms on eight elements, counted exactly

Every number below is measured, not estimated. n = 8, so $n(n-1)/2 = 28$.

Input	Bubble (comp, swap, passes)	Selection (comp, swap)	Insertion (comp, shift)
sorted [0..7]	7, 0, 1	28, 0	7, 0
reversed [7..0]	28, 28, 7	28, 4	28, 28
random [5,2,7,1,8,3,6,4]	25, 13, 5	28, 5	18, 13

Four readings, and each one answers a real question:

• Bubble sort with the early-exit flag is $O(n)$ on sorted input — 7 comparisons, one pass, and it stops. Without the flag it does all 28 comparisons and 7 passes regardless. That flag is the entire difference between ”$O(n^2)$ always” and ”$O(n)$ best case”, and it is one boolean.
• Selection sort does 28 comparisons on every input. Sorted, reversed, random — always exactly $n(n-1)/2$, because finding the minimum of the unsorted suffix requires scanning all of it no matter what. Selection sort is not adaptive at all, which is the cleanest way to state its weakness.
• But selection sort does the fewest swaps: 4 on reversed input, against bubble sort’s 28. It performs at most n - 1 swaps by construction, because each pass places one element permanently. That is why it wins when writes are expensive and reads are cheap.
• Insertion sort is the adaptive one. 7 comparisons on sorted input (one per element, each failing immediately), and its shift count equals the number of inversions — 28 on reversed input, 13 on the random one. Its true bound is $O(n + \text{inversions})$, which is why “nearly sorted” makes it linear.

Note bubble and insertion agree at 13 swaps/shifts on the random input. That is not coincidence: both only ever move an element past an adjacent larger one, so both perform exactly one move per inversion. Bubble sort just needs more comparisons to find them.

What “one pass” of bubble sort actually achieves

On reversed input, bubble sort needs 7 passes for 8 elements — n - 1. Each pass guarantees only that the largest remaining element reaches its final position, which is why the inner loop can shrink by one each time (range(n - 1 - i)). Nothing else is guaranteed; an element can be one slot from home and still take n - 1 passes to get there if it needs to move left.

That asymmetry is bubble sort’s real flaw. A large element moves right quickly — potentially all the way in a single pass — but a small element at the end moves left by exactly one slot per pass. The measured 7 passes on reversed input is that worst case: element 0 has to walk from index 7 to index 0, one step at a time.

Time and space complexity

Algorithm	Best	Average	Worst	Space	Stable?
Bubble sort	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	Yes
Selection sort	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	No
Insertion sort	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	Yes

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.

The variant map

Variant	The change	Where it matters
Bubble sort with early exit	A swapped flag; break when a pass makes no swaps	$O(n)$ best case instead of $O(n^2)$
Cocktail shaker sort	Alternate the pass direction	Fixes the “small element at the end” asymmetry
Binary insertion sort	Binary-search the insertion point	$O(n \log n)$ comparisons, still $O(n^2)$ shifts
Insertion sort on a linked list	Rewire instead of shifting	LC 147 — no shifting cost at all
Shell sort	Insertion sort over decreasing gaps	Sub-quadratic in practice, still elementary in spirit
Selection sort, min and max per pass	Halves the number of passes	Same comparison count
Gnome sort	Walk forward, step back while out of order	Insertion sort, written as one loop
Counting adjacent swaps to sort	Bubble sort’s swap count is the inversion count	2340 · minimum-adjacent-swap problems
Insertion sort as a fallback	Used below ~16-64 elements	Timsort, introsort, every production sort

Insertion sort is the one that is genuinely still used

Not as a general sort — as the base case. Timsort insertion-sorts runs shorter than 64 elements; introsort switches to it below ~16. The reason is that asymptotics lose to constants at small n: insertion sort has almost no overhead, walks memory sequentially, and on nearly-sorted data its $O(n + \text{inversions})$ bound is close to linear.

So “which $O(n^2)$ sort would you ever ship?” has a real answer, and it is this one, as a base case.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

3 problems

1 easy2 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○1051Height CheckereasyCount how many positions differ from the fully sorted order; a one-line use case once you have a working sort
• ○147Insertion Sort ListmediumThe same shifting idea, but on a linked list instead of an array
• ○912Sort an ArraymediumImplement any $O(n \log n)$ sort from scratch (a good excuse to compare against these $O(n^2)$ baselines)

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) <= 5000, 0 <= nums[i] <= 5000.

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

Why this test checks a property

The problem accepts any order with evens first, so a fixed expected list would reject correct answers. The test instead verifies the multiset is unchanged and no even appears after an odd.

pch.exerciseTag pch.exerciseTitle

Editorial

This is a partition, the elementary operation underneath quicksort: rearrange so everything satisfying a predicate comes first.

Time $O(n)$, one pass. Space $O(1)$.

The one-liner [n for n in nums if n % 2 == 0] + [n for n in nums if n % 2] is also correct and much shorter — worth saying — but it allocates $O(n)$ and makes two passes. The two-pointer version is in place.

Note the pointers are not symmetric in what they skip: left advances past evens (already correct), right retreats past odds (already correct), and only when both are looking at a misplaced value does a swap happen. Getting the parity checks backwards produces odds-first, which the property check catches.

Follow-ups: “Preserve the relative order within each group?” — that needs a stable partition, so the list-comprehension version, or $O(n)$ extra space. “Sort by parity of the index too (LC 922)?” — two write pointers stepping by 2. “Three categories?” — the Dutch national flag partition, which is LC 75.

LC 75 — Sort Colors · Medium

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

Constraints. 1 <= len(nums) <= 300, values are 0, 1 or 2.

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

pch.exerciseTag pch.exerciseTitle

Editorial

The Dutch national flag partition maintains three regions: [0, low) holds 0s, [low, i) holds 1s, and (high, end] holds 2s. Everything in [i, high] is still unclassified.

Time $O(n)$, one pass. Space $O(1)$.

The asymmetry is the whole problem. When you swap a 0 forward, the value arriving at i came from the 1s region and is therefore known to be a 1 — so i can advance safely. When you swap a 2 backward, the value arriving at i came from the unexamined region, so i must stay put and inspect it.

Advancing i in both branches passes [2,0,1] by luck and fails on inputs like [2,2,0], which is why [2,2,2] and [1,2,0] are in the tests.

The two-pass counting-sort answer — tally the three values, then overwrite — is simpler and perfectly acceptable unless one pass is required. Say it first.

Follow-ups: “Two passes with counting?” — have it ready as the baseline. “k colours instead of 3?” — counting sort generalises; the flag partition does not directly. “Why is this relevant to quicksort?” — it is the three-way partition that makes quicksort efficient on duplicate-heavy input, as in Quickselect.

LC 147 — Insertion Sort List · Medium

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

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

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

pch.exerciseTag pch.exerciseTitle

Editorial

Insertion sort on a list is arguably more natural than on an array: there is no shifting, only a splice. The dummy head means inserting at the front needs no special case.

Time $O(n^2)$ — each insertion scans the sorted prefix. Space $O(1)$.

Two details:

• Save nxt before rewiring. head.next is overwritten by the splice, so without saving it you lose the rest of the input.
• Restart from dummy. A singly linked list cannot be scanned backwards, so every insertion begins at the front. That restart is what makes it quadratic — and it is inherent to insertion sort, not a flaw in the implementation.

An optimisation worth mentioning: if the incoming node is already larger than the current tail, append it directly without scanning. That makes nearly-sorted input close to $O(n)$, which is exactly the property Timsort exploits at scale.

Follow-ups: “Sort it in $O(n \log n)$ instead?” — merge sort, which is LC 148 and the natural fit for lists. “Why is insertion sort still used?” — it is fast for small or nearly-sorted inputs, which is why real sorts fall back to it below a size threshold. “Insertion sort on an array?” — shifting instead of splicing, same $O(n^2)$.

Interview follow-ups

They ask	What they’re checking	The answer
“All three are $O(n^2)$. Does the choice matter?”	Whether $O$ is where your thinking stops	Yes, on three axes. Adaptivity: insertion is $O(n + \text{inversions})$, bubble with the flag is $O(n)$ on sorted input, selection is $\Theta(n^2)$ always. Swaps: selection does at most n-1, bubble does one per inversion. Online: only insertion sort can accept elements as they arrive
“Best case for each?”	Precision	Insertion $O(n)$ · bubble $O(n)$ only with the early-exit flag · selection $\Theta(n^2)$, because scanning for the minimum cannot be skipped. Measured on 8 sorted elements: 7, 7 and 28 comparisons
“Which is stable?”	Requirements	Bubble and insertion are, since they only swap adjacent out-of-order elements. Selection sort is not — its long-range swap can jump one equal element past another
“Writes are expensive — flash memory. Which sort?”	Reading the constraint	Selection sort: at most n - 1 swaps, the fewest of any comparison sort. Measured 4 swaps on reversed 8-element input against bubble sort’s 28
“Data arrives one element at a time”	Online algorithms	Insertion sort — it maintains a sorted prefix and never needs the whole input. The other two must see everything before they can place anything
“Why does insertion sort’s shift count equal the inversion count?”	Understanding, not recall	It only ever moves an element past an adjacent larger one, and each such move fixes exactly one inversion. So the shifts are the inversions — 28 on reversed input, 13 on the random one
“Would you ever ship an $O(n^2)$ sort?”	Practical judgement	Yes — insertion sort as a base case. Timsort uses it below 64 elements, introsort below ~16. At small n, its tiny constant and sequential memory access beat the asymptotically better algorithms
“Make bubble sort $O(n)$ on sorted input”	The one-line fix	A swapped flag, breaking when a pass makes no swaps. Without it: 28 comparisons and 7 passes on already-sorted input; with it: 7 and one pass
“Can you reduce insertion sort’s comparisons?”	Depth	Binary-search the insertion point: $O(n \log n)$ comparisons. The shifts stay $O(n^2)$ because the array still has to be physically moved, so the total bound is unchanged — worth saying, because it is a partial win, not a fix
“Why does bubble sort need n-1 passes on reversed input?”	Whether you know what a pass guarantees	Each pass only guarantees the largest remaining element reaches its place. A small element at the end moves left one slot per pass, so element 0 starting at index 7 needs 7 passes — measured

Self-check

pch.quizTag pch.quizDefaultTitle

1. On an already-sorted array of 8 elements, how many comparisons do bubble (with early exit), selection, and insertion sort make?

   A 28, 28, 28 -- all are O(n^2) B 7, 28, 7 -- selection sort is the only one that cannot exploit sortedness C 7, 7, 7 D 0, 28, 0
   pch.quizShowAnswer

   B — 7, 28, 7 -- selection sort is the only one that cannot exploit sortedness — Measured. Bubble with the flag makes one pass of 7 comparisons and stops; insertion makes one failing comparison per element. Selection sort makes all 28 regardless of input, because finding the minimum of the unsorted suffix requires scanning every element of it. That is the cleanest statement of its weakness: it is not adaptive at all.

2. Why is selection sort preferred when writes are far more expensive than reads?

   A It makes fewer comparisons B It performs at most n-1 swaps -- 4 on reversed 8-element input, against bubble sort's 28 C It is stable D It uses less memory
   pch.quizShowAnswer

   B — It performs at most n-1 swaps -- 4 on reversed 8-element input, against bubble sort's 28 — Each pass finds the minimum and places it with a single swap, so the swap count is bounded by n-1 by construction -- the fewest of any comparison sort. It makes the *most* comparisons of the three (always 28 here), which is exactly the right trade when reads are cheap and writes wear out the medium. It is also not stable.

3. Insertion sort's shift count on the random input was 13, and bubble sort's swap count was also 13. Coincidence?

   A Yes -- the counts happen to coincide at this size B No -- both only move an element past an ADJACENT larger one, so each performs exactly one move per inversion C No -- both are stable, which forces equal counts D Yes, and it breaks for n > 8
   pch.quizShowAnswer

   B — No -- both only move an element past an ADJACENT larger one, so each performs exactly one move per inversion — Each adjacent swap fixes exactly one inversion, so any algorithm restricted to adjacent moves performs exactly as many moves as there are inversions -- 28 on reversed input, 13 on the random one, for both. What differs is the *comparisons* needed to find them: bubble made 25, insertion 18. This is also why insertion sort's true bound is O(n + inversions).

4. Which of the three are stable?

   A All three B Bubble and insertion -- they only swap adjacent out-of-order elements; selection sort's long-range swap can reorder equal elements C Selection and insertion D Only insertion sort
   pch.quizShowAnswer

   B — Bubble and insertion -- they only swap adjacent out-of-order elements; selection sort's long-range swap can reorder equal elements — Stability follows from locality. If you only ever exchange neighbours that are strictly out of order, two equal elements are never exchanged. Selection sort swaps the minimum into position from an arbitrary distance away, and that jump can carry it past an equal element -- the same reason quicksort is unstable.

5. Bubble sort without the early-exit flag, on already-sorted input of 8 elements?

   A 7 comparisons and 1 pass B 28 comparisons and 7 passes -- it cannot tell that it is finished C 0 comparisons D It raises
   pch.quizShowAnswer

   B — 28 comparisons and 7 passes -- it cannot tell that it is finished — Measured both ways: 7 and 1 with the flag, 28 and 7 without. One boolean is the entire difference between a Theta(n^2) algorithm and one with an O(n) best case. It is also the only thing that makes bubble sort's best case any better than selection sort's.

6. Why does bubble sort need n-1 passes on reverse-sorted input?

   A Because every element is out of place B A pass only guarantees the LARGEST remaining element reaches its slot; a small element at the end moves left one slot per pass, so element 0 at index 7 needs 7 passes C Because the early-exit flag never triggers D Because the inner loop shrinks each pass
   pch.quizShowAnswer

   B — A pass only guarantees the LARGEST remaining element reaches its slot; a small element at the end moves left one slot per pass, so element 0 at index 7 needs 7 passes — The asymmetry is the point. A large element can travel arbitrarily far right in one pass, carried along by successive swaps, but a small element only ever moves left by one position per pass. Measured 7 passes for 8 elements. Cocktail shaker sort alternates the direction specifically to fix this.

7. Binary insertion sort binary-searches the insertion point. What does that improve?

   A The overall complexity, to O(n log n) B Only the comparison count, to O(n log n) -- the shifts are still O(n^2), so the total bound is unchanged C The space complexity D Nothing measurable
   pch.quizShowAnswer

   B — Only the comparison count, to O(n log n) -- the shifts are still O(n^2), so the total bound is unchanged — Finding *where* an element goes becomes logarithmic, but physically making room still means moving every element after that point. The total stays O(n^2), dominated by data movement. It is a genuine win when comparisons are expensive (long strings, custom comparators) and no help at all when they are cheap -- worth stating as a partial improvement rather than a fix.

8. Would you ever ship an O(n^2) sort?

   A No -- never, under any circumstances B Yes: insertion sort as a base case. Timsort uses it below 64 elements, introsort below ~16 C Yes -- bubble sort, for readability D Only for lists under 3 elements
   pch.quizShowAnswer

   B — Yes: insertion sort as a base case. Timsort uses it below 64 elements, introsort below ~16 — At small n, asymptotics lose to constants: insertion sort has almost no per-element overhead, walks memory sequentially, and on nearly-sorted data approaches O(n). Every production sort you have used relies on it for exactly this. Bubble sort has no such niche -- it is strictly dominated by insertion sort on every axis.

Recall card

• Nobody asks you to bubble sort. These matter for adaptivity, swap counts, and as base cases.
• Insertion sort is $O(n + \text{inversions})$ — its shift count is the inversion count (28 on reversed input, 13 on random, measured). Nearly sorted means nearly linear.
• Insertion sort is the only online one — it can accept elements as they arrive.
• It is also the only one still shipped, as a base case: Timsort below 64 elements, introsort below ~16.
• Selection sort always does $n(n-1)/2$ comparisons — 28 for n = 8, on every input. Not adaptive at all.
• But selection sort does at most n-1 swaps (4 on reversed input against bubble’s 28) — the fewest of any comparison sort. Choose it when writes are expensive.
• Bubble sort needs the swapped flag to be $O(n)$ on sorted input: 7 comparisons and 1 pass with it, 28 and 7 without.
• One bubble pass only places the largest remaining element. A small element at the end moves left one slot per pass, hence n-1 passes on reversed input.
• Bubble and insertion are stable; selection is not — long-range swaps break stability, same as quicksort.
• Binary insertion sort fixes the comparisons ($O(n \log n)$), not the shifts — the total stays $O(n^2)$.

Recap

• Bubble sort swaps adjacent out-of-order elements; a swapped 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.