A month-end invoice export copies every InvoiceLine into an ArrayList and sorts it with a helper the team wrote in an interview loop: scan the unsorted tail, swap the smallest remaining amount into the next slot, repeat. Forty lines in the test fixture. Four hundred thousand lines on Friday night. The export is correct. The job misses its window. Nobody stored the lines in a bad list. They reused a quadratic procedure past the n it can afford.
Insertion, selection, and bubble are nested-loop sorts; insertion is the one that still lives. Selection is swap-the-min-into-place. Bubble is adjacent swaps until a quiet pass — a name that survives interviews. None of them are what you call on the export path.
This post is those three procedures. Families and the catalog live on the Algorithms Roadmap. Here we only care why insertion still shows up, why selection always pays the nested scan, and why bubble is not a production default.
Three nested loops, one bill
All three grow a sorted prefix with a loop nested in a loop. Worst case they compare on the order of n² pairs. That is cheap at n = 40. It is the month-end timeout at n = 400_000.
They are not the same loop:
| Procedure | Inner work | Why you would still type it |
|---|---|---|
| Insertion | Slide the next key left into the already-sorted prefix | Small n, nearly sorted data, short runs inside Timsort |
| Selection | Find the min of the unsorted tail, swap it into place | A teaching story; almost never a production reason |
| Bubble | Swap adjacent inversions until a pass makes no swap | Interviews, and the phrase “bubble up” |
A correct quadratic sort is still the wrong default on the invoice file. Object Arrays.sort is Timsort. Merge sort is the stable divide-and-conquer next in this wave.
Insertion: grow a sorted prefix
Index 0 is a sorted prefix of length one. For each later index i, take key = a[i] and slide every larger prefix entry one slot right until key fits. The prefix a[0 .. i] is then sorted. After i reaches the end, the whole array is.
a = [5, 2, 4, 6, 1, 3]
0 1 2 3 4 5
i=1 key=2 5>2 slide 5 → [2, 5, 4, 6, 1, 3]
i=2 key=4 5>4 slide 5 → [2, 4, 5, 6, 1, 3]
i=3 key=6 5<6 already → [2, 4, 5, 6, 1, 3]
i=4 key=1 slide 6, 5, 4, 2 → [1, 2, 4, 5, 6, 3]
i=5 key=3 slide 6, 5, 4 → [1, 2, 3, 4, 5, 6]Each i does work proportional to how far key must travel. Already-sorted input travels zero slots: one comparison per i, about n comparisons. One inversion at the end still slides once. Reverse-sorted input slides the whole prefix every time — that is the quadratic worst case.
nearly sorted [1, 2, 3, 4, 6, 5]
i=5 key=5 slide 6 once → [1, 2, 3, 4, 5, 6]
reversed [6, 5, 4, 3, 2, 1]
each key slides the whole prefix → 15 slides for n=6Same n. Different leftover order. Different bill. That is why insertion still earns a seat: nearly sorted data is cheap, and a tiny array is cheap even when it is not. Timsort insertion-sorts short natural runs for the same reason.
static void insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}The inner while uses > so equal keys do not slide: the new key stays to the right of earlier equals. That is the stable variant. Binary-searching the insertion point does not change the bill — you still slide the tail.
Note: Insertion mutates the array. If callers still hold indexes into the unsorted layout, those indexes are now lies.
Selection: swap the min into place
For each prefix index i, scan a[i .. n) for the minimum, then swap that slot with i. After i, the prefix is the smallest i + 1 values, in order. You never look at a[0 .. i] again.
a = [5, 2, 4, 6, 1, 3]
i=0 min at index 4 (1) swap 5↔1 → [1, 2, 4, 6, 5, 3]
i=1 min at index 1 (2) already → [1, 2, 4, 6, 5, 3]
i=2 min at index 5 (3) swap 4↔3 → [1, 2, 3, 6, 5, 4]
i=3 min at index 5 (4) swap 6↔4 → [1, 2, 3, 4, 5, 6]
i=4 min at index 4 (5) already → [1, 2, 3, 4, 5, 6]The inner scan always walks the whole tail. Already-sorted input still does every comparison. Swaps are few — at most n - 1 — but comparisons are not. That is the whole selection story: you paid quadratic comparisons to minimize swaps, which is the wrong trade on a Java int[] and a worse trade on an InvoiceLine[] whose compare is a timestamp plus three fields.
static void selectionSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int min = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) {
min = j;
}
}
int tmp = a[i];
a[i] = a[min];
a[min] = tmp;
}
}A swap of two equal keys can reorder them. Selection is not the stable procedure. There is no early-exit gift: finding that min == i still required the full tail scan.
Bubble: adjacent swaps until a quiet pass
Walk the array, swap a[j] and a[j + 1] whenever they are out of order, and repeat. Each pass floats the next-largest value to the end (the “bubble”). If a pass makes no swap, the array is sorted and you can stop.
a = [5, 2, 4, 6, 1, 3]
pass 1: 5↔2, 5↔4, 6↔1, 6↔3 → [2, 4, 5, 1, 3, 6] 6 in place
pass 2: 5↔1, 5↔3 → [2, 4, 1, 3, 5, 6]
pass 3: 4↔1, 4↔3 → [2, 1, 3, 4, 5, 6]
pass 4: 2↔1 → [1, 2, 3, 4, 5, 6]
pass 5: no swap → doneAlready-sorted input: one quiet pass, about n comparisons. Reverse-sorted input: every adjacent pair swaps, every pass. The early-exit flag is real. It does not make bubble a production sort. You still nested two loops, you still wrote more code than Arrays.sort, and a nearly-sorted array with one small value at the end still crawls left one slot per pass.
Bubble survives as a whiteboard name, not as a method you ship. If an interview asks you to sort without the library, insertion is the quadratic you can defend; the JDK call is the one you should name for production.
Do not paste a bubble helper next to the invoice export. The adjacent-swap loop is the procedure. Shipping it is the cargo-cult of the name. A cocktail/shaker variant that also bubbles small values left is the same nested bill with a different pass shape — still not a production sort.
Complexity
Use the words; the hub owns the glossary. Insertion and the adjacent-swap bubble with a no-swap exit are stable. Selection is not. All three can run in-place.
| Insertion | Selection | Bubble (early exit) | |
|---|---|---|---|
| Best time | O(n) already sorted | O(n²) always | O(n) already sorted |
| Worst time | O(n²) reversed | O(n²) | O(n²) reversed |
| Extra space | O(1) | O(1) | O(1) |
| Stable | Yes (> not >=) | No | Yes (> not >=) |
| In-place | Yes | Yes | Yes |
At n = 400_000, n² comparisons is on the order of 1.6 × 10¹¹. The month-end job is not “a bit slow.” It is the wrong family. Object Arrays.sort is Timsort — about n log n worst, linear when the input is already one run. Primitive Arrays.sort is dual-pivot quicksort, a later post.
When not to use a quadratic sort
Skip these loops when the job is “sort this collection” past a tiny n:
- The export, the audit dump, the request log. Thousands of rows and up. Call
Arrays.sort/List.sort. Do not “optimize” bubble into selection and ship that. - You needed a sorted snapshot once. Sort with the JDK and keep the result. Re-running insertion on every dashboard refresh to “keep it sorted” is the same cargo-cult as sorting on every lookup.
- Online inserts into a large array. Sliding the tail on every insert is insertion sort’s inner loop billed per write. That is the array’s cost, not a reason to name a sort. If inserts and ordered scans are both hot, a tree is a different job.
- Interview muscle memory on a service path. A correct bubble sort is still the wrong default at a million rows.
Keep insertion in mind for n that fits in a cache line, a nearly-sorted buffer, and as the reason Timsort does not merge runs of length two. That is literacy. It is not a license to replace Arrays.sort.
JDK: there is no InsertionSort class
The library you call is the sort you already have:
Arrays.sorton an arrayList.sort/Collections.sorton aList
Object overloads run Timsort. Primitive overloads run dual-pivot quicksort. Neither is insertion, selection, or bubble.
InvoiceLine[] lines = ...;
Arrays.sort(lines, Comparator.comparing(InvoiceLine::amount));
List<InvoiceLine> list = ...;
list.sort(Comparator.comparing(InvoiceLine::amount));Hand-roll insertion only when you are teaching the loop, writing a test of the idea, or looking at a slice so small the JDK call’s constant factors are the joke — a five-element config table. Even then the JDK call is one line and correct.
Production sort of objects → Arrays.sort / List.sort. Do not ship selectionSort because it “only swaps n times.”
Note: Collections.sort on a List of objects is Timsort as well. Sorting int[] is not this family and not this post.
Cheat sheet
Insertion: slide a[i] left into sorted prefix; cheap if nearly sorted
Selection: min of tail, swap into a[i]; comparisons always ~ n²
Bubble: adjacent swaps; early exit exists; do not ship it
Best case: insertion/bubble O(n) if already sorted; selection still O(n²)
Worst: O(n²) for all three
Still lives: insertion on small n, short Timsort runs
Do not: quadratic-sort the invoice export
JDK: Arrays.sort / List.sort (Timsort on objects)Do:
- Use insertion as the mental model for a tiny or nearly-sorted range, and as the inner step Timsort already runs.
- Name selection as “swap min into place” so you can reject it when someone is counting swaps instead of comparisons.
- Call the JDK for anything that looks like production data.
Don’t:
- Paste an interview bubble/selection helper onto a batch job because it was correct on forty rows.
- Pick selection to “save swaps” on objects whose compare is the expensive part.
- Treat a quiet-pass bubble as an adaptive production sort. Adaptive and production is Timsort.
Wrap-up
Insertion, selection, and bubble are the nested-loop sorts. Insertion grows a sorted prefix by sliding; it is cheap when little is out of order, and it is the reason short runs do not need a merge. Selection always scans the tail for the next min. Bubble swaps neighbors until a pass is quiet — a story you can tell on a whiteboard, not a method you merge.
For the invoice file, call Arrays.sort. What that call does on objects is Timsort. The next procedure in this wave is the stable divide-and-conquer that sort family is built from.