Sorting Algorithms — Head to Head

⚡ Default in-memory sort → Quick Sort

Best average-case speed with tiny constants and in-place O(log n) memory. It is what most language runtimes use (often as part of an introsort) for arrays of primitives. Watch it lose on the Reversed distribution — a naive last-element pivot degrades to O(n²).

🔀 Need stability or guaranteed O(n log n) → Merge Sort

Never worse than O(n log n) and stable (equal keys keep their order), which matters when sorting records by a secondary field. The cost is O(n) extra memory, so it shines for linked lists and huge on-disk (external) sorts.

⛰️ Tight memory, no worst-case risk → Heap Sort

In-place and guaranteed O(n log n) even in the worst case — no pathological input like Quick Sort. It is not stable and has poorer cache locality, so it is usually a bit slower in practice than Quick Sort.

📥 Small or nearly-sorted data → Insertion Sort

O(n) on nearly-sorted input (try the Nearly-sorted distribution — it often beats the O(n log n) sorts here) and extremely low overhead. Standard libraries switch to it for tiny subarrays inside Quick/Merge sort.

🔢 Small integer range → Counting / Radix Sort

Non-comparison sorts that break the O(n log n) comparison lower bound. Counting Sort is O(n + k) for values in a small range k; Radix Sort is O(n·d) for d-digit integers. Unbeatable for things like ages, ports, or fixed-width IDs — useless for arbitrary objects.

🎓 Teaching only → Bubble / Selection Sort

Both are O(n²) and almost always the slowest here. Selection Sort minimizes writes (≤ n swaps) if writes are very expensive; Bubble Sort’s only merit is detecting an already-sorted array in one O(n) pass. Avoid in production.