Comparison Sorts — Bubble, Selection, Insertion

The three elementary comparison sorts — bubble, selection, insertion — are O(n²) and rarely used in production, but interviews use them to test whether you know their trade-offs: stability, adaptivity, and best/worst cases. Insertion sort in particular is genuinely useful for small or nearly-sorted data.

The core idea

All three build a sorted region incrementally:

• Bubble sort: repeatedly swap adjacent out-of-order pairs; largest "bubbles" to the end. O(n²), O(n) best with an early-exit flag, stable.
• Selection sort: repeatedly pick the minimum and place it; O(n²) in all cases, not stable, but minimises the number of swaps (n−1).
• Insertion sort: insert each element into the sorted prefix; O(n²) worst, O(n) on nearly-sorted data (adaptive), stable — the best elementary sort in practice.

Sort	Best	Avg/Worst	Space	Stable	Adaptive
Bubble	O(n)	O(n²)	O(1)	Yes	Yes (flag)
Selection	O(n²)	O(n²)	O(1)	No	No
Insertion	O(n)	O(n²)	O(1)	Yes	Yes

Exam Tricks & Tips

• 🎯 Insertion sort is O(n) on nearly-sorted input — the "adaptive" winner among the three.
• 🎯 Selection sort is O(n²) even on sorted data, but makes only O(n) swaps (useful when writes are costly).
• 🎯 Bubble sort with an early-exit flag becomes O(n) on already-sorted input.
• 🎯 Stability: bubble and insertion are stable; selection is not.
• 🎯 All are O(1) space (in-place) — their only real advantage over merge sort.
• ❌ Common mistake: claiming selection sort is O(n) on sorted input — it always scans for the min, so O(n²).

Expected pattern

"Which sort is stable / adaptive / best for nearly-sorted data?", or implement one and analyse it. Interviewers probe the best-case differences and stability rather than raw coding.

Quick recap

Bubble, selection, insertion are O(n²), O(1)-space comparison sorts. Insertion is adaptive (O(n) nearly-sorted) and stable; bubble is stable with an early-exit best case; selection is always O(n²) and unstable but minimises swaps.

Cover the answer, recall, then check. 11 cards on elementary comparison sorts.

Q1. Time complexity of bubble, selection, and insertion sort (average)?
A1. O(n²) for all three.

Q2. Which elementary sort is O(n) on nearly-sorted data?
A2. Insertion sort — it's adaptive.

Q3. Why is selection sort O(n²) even on sorted input?
A3. It always scans the unsorted region to find the minimum, regardless of order.

Q4. Which of the three are stable?
A4. Bubble and insertion; selection sort is not stable.

Q5. Space complexity of all three?
A5. O(1) — they sort in place.

Q6. Selection sort's one advantage?
A6. It makes only O(n) swaps (n−1), useful when writes/swaps are expensive.

Q7. How does bubble sort achieve an O(n) best case?
A7. An early-exit flag stops once a full pass makes no swaps (already sorted).

Q8. What does "adaptive" mean for a sort?
A8. Its running time improves when the input is partially sorted.

Q9. Best elementary sort in practice, and why?
A9. Insertion sort — adaptive, stable, low overhead, great for small arrays.

Q10. Why do library sorts switch to insertion sort for small subarrays?
A10. Its low constant factors beat O(n log n) sorts on tiny inputs (e.g., Timsort/introsort cutoffs).

Q11. Number of comparisons in selection sort?
A11. ~n²/2 always — it's not affected by initial order.

The three elementary sorts are rarely the fastest, but interviewers ask about them to test whether you understand stability, adaptivity, and why O(n²) happens. Insertion sort in particular is genuinely useful on small or nearly-sorted data.

Core idea: all three build sorted order by comparing and swapping adjacent-ish elements. They are simple, in-place, and O(n²) in the worst case — but they differ in stability and best-case behaviour, which is exactly what gets probed.

How it works

Beginner — the three algorithms

• Bubble sort: repeatedly swap adjacent out-of-order pairs; the largest "bubbles" to the end each pass. O(n²).
• Selection sort: each pass selects the minimum of the unsorted part and places it next. Always O(n²), even if sorted.
• Insertion sort: grow a sorted prefix by inserting each new element into its place, shifting larger ones right.

for i in 1..n-1:               # insertion sort
    key = a[i]; j = i-1
    while j >= 0 and a[j] > key:
        a[j+1] = a[j]; j -= 1
    a[j+1] = key

Intermediate — the distinguishing properties

Sort	Best	Worst	Stable?	Adaptive?
Bubble	O(n)*	O(n²)	Yes	Yes (with early-exit flag)
Selection	O(n²)	O(n²)	No	No
Insertion	O(n)	O(n²)	Yes	Yes
All are in-place, O(1) space. *Bubble is O(n) only with an early-exit optimisation.

Advanced — why insertion sort matters in practice

Insertion sort is O(n) on nearly-sorted data and has tiny constants, so real libraries (Timsort, introsort) switch to it for small subarrays (≈ ≤ 16 elements). Selection sort minimises the number of swaps (n−1), useful when writes are expensive. Understanding "adaptive" (fast on almost-sorted input) and "stable" (equal keys keep their order) is the real exam content.

Worked example

Insertion sort [5, 2, 4, 1]. Insert 2 before 5 → [2,5,4,1]. Insert 4 between 2,5 → [2,4,5,1]. Insert 1 at front, shifting 2,4,5 → [1,2,4,5]. Total comparisons scale with inversions; on this small nearly-random array it's cheap, and on an already-sorted array each element inserts with one comparison → O(n).

When to use it

• Insertion sort: small arrays, nearly-sorted data, online sorting (elements arriving one at a time), the base case inside quicksort/mergesort.
• Selection sort: when write/swap cost dominates (e.g. flash memory).
• Bubble sort: essentially never in practice — but a favourite for explaining stability and passes.

Tricks & gotchas

• Stability matters when sorting by a secondary key — selection sort is not stable.
• Bubble sort is only O(n) best-case if you add an early-exit flag when a pass makes no swaps.
• "Nearly sorted" or "small n" is the signal for insertion sort, not a fancy O(n log n) sort.
• Mnemonic: "Insertion is adaptive and stable; selection minimises swaps; bubble is for teaching."

Key complexities

• Bubble/Selection/Insertion: O(n²) worst and average; O(n) best for insertion (nearly sorted).
• Selection sort: always O(n²), O(n) swaps.
• Comparison-sort lower bound: Ω(n log n) (decision tree has n! leaves).
• Insertion sort runs in Θ(n + inversions).
• Stability: bubble and insertion stable; selection not.
• All are in-place, O(1) extra space.

Usage: prefer insertion sort for small or nearly-sorted inputs.

Worked Example

Problem: Sort [64, 25, 12, 22, 11] using selection sort, showing each pass.

Solution: Selection sort repeatedly finds the minimum of the unsorted suffix and swaps it into the next position.

pass	find min of unsorted part	swap	array
1	min = 11	with 64	[11, 25, 12, 22, 64]
2	min = 12	with 25	[11, 12, 25, 22, 64]
3	min = 22	with 25	[11, 12, 22, 25, 64]
4	min = 25	already in place	[11, 12, 22, 25, 64]

After 4 passes the array is sorted: [11, 12, 22, 25, 64].

Selection sort always does ~n²/2 comparisons regardless of input → O(n²) time, O(1) space, and it is not stable.

Answer: [11, 12, 22, 25, 64].