What this module covers: Before the two sorts that actually get used in production (Modules P-9, P-10), it's worth building — and clearly seeing the cost of — the three sorts everyone encounters first: bubble, selection, and insertion. All three are O(n²), all three are correct, and understanding exactly why they're O(n²) is what makes merge sort and quick sort's O(n log n) feel like a real, earned improvement rather than a magic number to memorize.
Bubble sort repeatedly scans the array, swapping any adjacent pair that's out of order — each full pass "bubbles" the largest remaining unsorted value to its correct position at the end.
typescript
The outer loop runs n times; the inner loop, for each outer iteration, checks roughly n more adjacent pairs. That's the identical nested-loop shape flagged as O(n²) back in Module F-1 — n × n comparisons in the worst case, each one only fixing a single adjacent pair before moving on.
Selection Sort: Repeatedly Find the Minimum
Selection sort takes a different approach to the same cost: on each pass, scan the entire remaining unsorted portion to find its minimum, then swap that minimum into its correct position.
typescript
Same O(n²) shape, arrived at differently: n outer iterations, each doing an O(n) scan to find the minimum. The one practical difference from bubble sort worth naming: selection sort performs at most n swaps total (one per outer iteration), while bubble sort can perform up to O(n²) swaps — a real difference if swaps are expensive (say, swapping large objects rather than plain numbers), even though both are the same Big-O time class.
Insertion Sort: Build Up a Sorted Prefix
Insertion sort grows a sorted region from the left, inserting each new element into its correct position within that already-sorted prefix:
typescript
Worst case (input in reverse order) is still O(n²) — each new element might need to shift all the way through the entire sorted prefix. But insertion sort has a property the other two don't: on already-nearly-sorted input, it's close to O(n), because the while loop barely runs at all when each new element is already close to its correct position. This isn't just a theoretical curiosity — it's exactly why some production sort implementations switch to insertion sort for small subarrays (often somewhere under 10-20 elements) even inside an otherwise O(n log n) algorithm: below a certain size, insertion sort's low overhead and near-linear behavior on partially-ordered data beats the overhead of further recursive splitting.
Why All Three Are O(n²), and Why That's Worth Feeling, Not Just Knowing
All three sorts share the same fundamental limitation: they only ever compare and fix relationships between nearby elements (bubble: adjacent pairs; selection: current position vs. remaining minimum; insertion: current element vs. its immediate sorted neighbors) — none of them make a decision that eliminates large chunks of remaining work in one move, the way binary search (Module F-11) or the merge step in Module P-9 will.
typescript
Sorting 10 items this way costs ~100 operations — trivial. Sorting 10,000 items costs ~100,000,000 — the same O(n²) production-latency cliff from Module F-1's table, now applied to something as ordinary-sounding as "sort this list before displaying it."
Where This Shows Up in Your Stack
Array.prototype.sort() in V8 (Node.js/Chrome) uses a hybrid strategy: insertion sort for small arrays (roughly 10-ish elements or fewer) where its low overhead wins, and Timsort-family algorithms (merge-sort-based) for larger arrays — you get the benefit of insertion sort's simplicity at small scale without paying its O(n²) cost at large scale, entirely transparently.
"Nearly sorted" data shows up constantly in production: a live leaderboard where scores change slightly between refreshes, a log stream that's mostly chronological with occasional out-of-order arrivals — insertion sort's near-O(n) behavior on this kind of input is a genuine, practical reason it isn't purely a teaching exercise.
Small, fixed-size sorts embedded in hot paths — sorting a handful of candidate values inside a request handler, for instance — are exactly where an O(n²) sort's simplicity and low constant-factor overhead can beat a "smarter" O(n log n) algorithm's setup cost, since n is small enough that the difference between n² and n log n barely registers.
Summary
Bubble, selection, and insertion sort are all O(n²) in the worst case, because each only fixes local, nearby relationships rather than eliminating large chunks of remaining work per step.
Bubble sort repeatedly swaps adjacent out-of-order pairs; selection sort repeatedly finds and places the minimum of the remaining unsorted region; insertion sort grows a sorted prefix by inserting each new element into its correct position within it.
Insertion sort is close to O(n) on nearly-sorted input — a genuine practical advantage, and the reason production sort implementations often fall back to it for small subarrays.
The shared bottleneck across all three: none of them make a single comparison that rules out a large fraction of remaining work, unlike binary search or the divide-and-conquer sorts coming next.
V8's actual Array.prototype.sort() is a hybrid — insertion sort for small arrays, a merge-sort-family algorithm for larger ones — a real-world instance of choosing the right tool based on input size, not defaulting to one algorithm everywhere.
The next module, Sorting II: Merge Sort and Divide-and-Conquer, introduces the technique that breaks past the O(n²) ceiling — splitting the problem in half repeatedly, rather than only ever comparing nearby elements.
Knowledge Check
What is the fundamental reason all three sorts covered in this module — bubble, selection, and insertion — share the same O(n²) worst-case time complexity, despite implementing visibly different logic?
Why does the module state that insertion sort performs close to O(n) on already-nearly-sorted input, even though its worst-case complexity is O(n²)?
According to the module, why does V8's actual Array.prototype.sort() implementation use insertion sort for small arrays, rather than using its more sophisticated merge-sort-family algorithm for every array size?
Test your knowledge with more question sets
Sign in to access a wider variety of questions and get notified when new practice sets are added to this module.
functionbubbleSort(nums:number[]):number[]{const arr =[...nums];for(let i =0; i < arr.length; i++){for(let j =0; j < arr.length - i -1; j++){if(arr[j]> arr[j +1]){[arr[j], arr[j +1]]=[arr[j +1], arr[j]];// swap adjacent out-of-order pair}}}return arr;}
functionselectionSort(nums:number[]):number[]{const arr =[...nums];for(let i =0; i < arr.length; i++){let minIndex = i;for(let j = i +1; j < arr.length; j++){if(arr[j]< arr[minIndex]) minIndex = j;// track the smallest remaining value's index}[arr[i], arr[minIndex]]=[arr[minIndex], arr[i]];// one swap per outer iteration}return arr;}
functioninsertionSort(nums:number[]):number[]{const arr =[...nums];for(let i =1; i < arr.length; i++){const current = arr[i];let j = i -1;while(j >=0&& arr[j]> current){ arr[j +1]= arr[j];// shift larger elements right to make room j--;} arr[j +1]= current;}return arr;}
// The shared bottleneck, made explicit: n outer iterations, each doing O(n) work// Regardless of exactly what that O(n) work is (swap-scan, find-min, shift-insert),// n × O(n) = O(n²) is unavoidable with this "local, incremental fix" strategy.