Sorting algorithms

Sorting algorithms fall into two families.

The simple `O(n²)` family — short code, and genuinely fast on small arrays:

• Bubble sort — compares and swaps neighbours; with a "nothing changed" flag it is O(n) on an already sorted array. Essentially unused in real code, kept for teaching
• Insertion sort — "inserts" each element into the sorted part on its left. Very fast on nearly sorted data (close to O(n)), which is exactly why real libraries use it for small chunks
• Selection sort — each pass finds the minimum and moves it to the front. Always O(n²) no matter how good the data is. Its one virtue: a minimal number of swaps (O(n)), which matters on memory where writes are very expensive

The efficient `O(n log n)` family:

• Merge sort — split in half, sort each half, merge. O(n log n) in all cases, stable, but needs O(n) extra memory. Indispensable on linked lists and for external (on-disk) sorting
• Quicksort — pick a pivot, put smaller values left and larger right, then recurse. O(n log n) on average and the fastest in practice, but O(n²) with poor pivot choices. Not stable
• Heap sort — build a heap from the array and pop the maximum repeatedly. O(n log n) in all cases with O(1) extra memory, but poor cache behaviour makes it slower than quicksort in practice. Not stable

Why can't anything beat `O(n log n)`? This question probes theoretical depth, and the answer is simpler than you'd expect.

Picture a comparison-based sorting algorithm as a decision tree: each comparison yields one of two outcomes, so the tree branches in two. n elements have n! possible orderings, so the tree needs at least n! leaves — one per possible answer. A binary tree of height h has at most 2^h leaves, so 2^h ≥ n!, i.e. h ≥ log₂(n!). By Stirling's formula log₂(n!) ≈ n log₂ n.

Conclusion: any algorithm that only compares elements to each other must make `n log n` comparisons in the worst case. That is not a weakness of a particular algorithm but an information-theoretic bound.

How do you get past it? By not comparing. If you can exploit the internal structure of the elements:

• Counting sort — when values lie in a bounded range (0..k), you just count how often each value occurs: O(n + k). Perfect for sorting a million users by age (0-120)
• Radix sort — sorts digit by digit (or byte by byte): O(d × (n + k)). For fixed-length keys (IDs, dates)

These algorithms don't "cheat" the bound — they simply use extra information (the value range). Stressing that in an interview is a strong signal.

What is actually used in practice? This is the more useful question, because you don't hand-write quicksort in real code.

• JavaScript — Array.prototype.sort is required to be stable since ES2019. V8 uses TimSort: a merge/insertion hybrid that detects already-sorted stretches ("runs") and is very fast on real data. The critical trap: the default comparison is by string — [10, 9, 1].sort() gives you [1, 10, 9]. For numbers a comparator is mandatory: sort((a, b) => a - b)
• Kotlin/JVM — for objects, sorted(), sortedBy and sortedWith call TimSort underneath and are stable. Primitive arrays (IntArray.sort()) use dual-pivot quicksort and are not stable — though with primitives equal values are indistinguishable, so there is no practical consequence
• Dart — List.sort() is not guaranteed stable (the docs say so explicitly). When stability matters you use mergeSort from package:collection. This becomes a real problem in Flutter when sorting a list by multiple criteria

The rule: use the built-in sort. Library implementations have been optimised for years — hybrid strategies, insertion sort for small chunks, run detection, cache-friendly memory patterns. Writing your own quicksort needs a solid reason: unusual memory constraints, external sorting, or not needing a sort at all (for top-K a heap is enough).