Basic Sorting

Sorting feels like a solved problem — every language has \sort()\ built in — but the *basic* sorts (Bubble, Selection, Insertion) are still worth knowing well. Real production sorts (Timsort, Introsort) are hybrids that fall back to insertion sort on small partitions. Plus, the only way to genuinely understand "why is O(n log n) the limit?" is to first feel the pain of O(n²).

What "Basic Sorting" Actually Is

The three classic O(n²) algorithms — Bubble, Selection, Insertion — all do the same job (rearrange an array into order) using only comparisons and swaps of adjacent or nearby elements. They differ in which pair to compare next and how many swaps it takes. Each one teaches a different lesson, and each one wins in some real situation.

Daily Mental Model

Imagine sorting a hand of playing cards.

• Bubble — keep walking through the cards swapping adjacent out-of-order pairs until no swaps happen.
• Selection — scan the unsorted region, pick out the smallest, swap it to the front.
• Insertion — pick up cards one at a time and insert each into its right place among the cards already sorted. (This is what people actually do with cards.)

Beginner Mistakes to Skip

1. Not adding the "did anything swap?" flag to bubble sort. Without it, bubble sort is O(n²) on already-sorted input. *With* it, it's O(n). 2. Confusing "stable" with "in-place". They're orthogonal. Stable = equal elements keep relative order. In-place = O(1) extra space. Insertion sort is both. Selection sort is in-place but not stable. 3. Saying "Selection Sort is the worst because it's O(n²)". It's the worst on *time* but the best on writes (exactly n − 1 swaps). On hardware where writes are expensive (EEPROM, flash) selection sort wins. 4. Forgetting that insertion sort is O(n) on nearly-sorted data. This is *why* Timsort uses it. 5. Using bubble sort in production. Don't. There is essentially no input on which bubble sort is the right choice over insertion sort. Outside teaching, treat it as folklore. 6. Sorting a 1,000,000-element array with bubble sort to "see how long it takes" — and then concluding "sorting is slow". You measured the wrong algorithm.

Intermediate: Bubble Sort with the Early-Exit Flag

\\\`js function bubble(arr) { const n = arr.length; for (let i = 0; i < n - 1; i++) { let swapped = false; for (let j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; swapped = true; } } if (!swapped) break; // already sorted } return arr; } \\\`

• Time: O(n²) average / worst, O(n) best (with the flag, on sorted input).
• Space: O(1). Stable: yes.
• After pass \i\, the largest \i + 1\ elements are guaranteed to be at the end — that's why the inner bound is \n - 1 - i\.

Intermediate: Selection Sort

\\\`js function selection(arr) { const n = arr.length; for (let i = 0; i < n - 1; i++) { let min = i; for (let j = i + 1; j < n; j++) { if (arr[j] < arr[min]) min = j; } if (min !== i) [arr[i], arr[min]] = [arr[min], arr[i]]; } return arr; } \\\`

• Time: O(n²) in all cases — no best-case shortcut, because we always scan the rest of the array to find the min.
• Space: O(1). Stable: no (the long swap can leapfrog an equal element). Writes: at most n − 1 swaps — the lowest of any comparison sort.

Intermediate: Insertion Sort — the Practical Hero

\\\`js function insertion(arr) { for (let i = 1; i < arr.length; i++) { const key = arr[i]; let j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; // shift right j--; } arr[j + 1] = key; } return arr; } \\\`

• Time: O(n²) worst, O(n) best on already-sorted, O(n + d) where \d\ is the number of inversions.
• Space: O(1). Stable: yes (only moves elements past strictly greater ones).
• Adaptive: runs in nearly O(n) on nearly-sorted data — *which is what most real-world data looks like*.

Advanced: Stability — Why It Matters

A sort is stable if equal elements keep their original relative order. Real example:

\\\` records = [{name:"Ana", score:90}, {name:"Bo", score:80}, {name:"Cy", score:90}] sortByScore(records) // stable → Ana still before Cy among score=90 \\\`

You need stability when sorting by multiple keys in passes: first sort by secondary key, then by primary key — only stable sort preserves the secondary order inside ties.

Advanced: When O(n²) Beats O(n log n)

The asymptotic win of merge/quicksort doesn't kick in for small \n\. Constants and overhead matter. Real numbers:

• For n ≤ ~16, insertion sort is faster than quicksort or mergesort because it has tiny constants and excellent cache behaviour.
• This is why Timsort (Python, Java) and Introsort (C++) switch to insertion sort for small partitions.
• For nearly-sorted data with O(n) inversions, insertion sort is O(n) — beating the O(n log n) lower bound, which only applies to fully-shuffled input.

Advanced: In-Place vs Out-of-Place, and Adaptive vs Non-Adaptive

"Adaptive" means *the algorithm gets faster on already-mostly-sorted input*. Insertion sort is the gold standard.

Advanced: How Real Sort Libraries Use the Basics

• Python \sorted()\ → Timsort: scans for natural runs, extends short runs with binary insertion sort, then merges.
• Java \Arrays.sort(Object[])\ → Timsort. \Arrays.sort(int[])\ → Dual-Pivot Quicksort with insertion sort under threshold.
• C++ \std::sort\ → Introsort: Quicksort, falls back to Heapsort if recursion is too deep, and Insertion sort for small partitions.
• Rust \sort\ → stable variant of Timsort (PDQ-mergesort).
• V8 (JavaScript) → Timsort since 2018.

Advanced: Comparison Cheat Sheet

Practice Path

1. Implement bubble sort without the early-exit flag, then add it. Time both on \[1,2,3,…,1000]\ (already sorted) — note the difference. 2. Implement selection sort. Verify it makes at most n − 1 swaps by counting them on a random array of size 100. 3. Implement insertion sort. Run it on \[1,2,3,…,1000]\, then on \[1000,…,1]\. Compare the comparison counts — best vs worst case in action. 4. Write binary insertion sort: same algorithm but use binary search to find where to insert. Same O(n²) total work (still O(n) shifts) but fewer comparisons — useful when comparison is expensive (e.g., comparing long strings).