Choosing a sorting algorithm, and spotting a sorting…
Choosing a sorting algorithm, and spotting a sorting question
There's no single best sort. Each algorithm in this introduction wins somewhere — small arrays, nearly sorted data, guaranteed speed, little memory, stability, or small integer keys. This lesson puts them side by side, shows what your language's built-in sort actually does, and how to recognise an interview question that sorting will crack.
What your language's sort uses
Built-in sorts are hybrids that combine the strengths above. Use them unless a question asks you to implement a sort, or a special key (small integers) makes a linear sort possible.
JavaScriptArray.prototype.sort — Timsort in V8, and stable by specification since 2019. Pass a comparator for numbers.
Pythonsorted / list.sort — Timsort (a merge sort that finds already-sorted runs and uses insertion sort on short ones). Stable, O(n) on sorted input.
JavaArrays.sort — dual-pivot quick sort for primitive arrays (not stable, but nobody can tell equal ints apart), Timsort for objects and Collections.sort (stable).
C++std::sort — introsort: quick sort, switching to heap sort if recursion gets too deep and insertion sort for small ranges. Not stable; use std::stable_sort (merge sort) when it must be.
A decision guide
A few dozen values, or nearly sorted → insertion sort.
Need stable, or a guaranteed O(n log n), or sorting a linked list → merge sort.
A big array in memory, speed first → quick sort with a random pivot (or the built-in sort).
O(n log n) guaranteed with O(1) extra memory → heap sort (see the Heap course).
Integers in a small range → counting sort. Fixed-width integers or strings, lots of them → radix sort.
Only the top k or the k-th value → don't sort everything: a heap or quickselect does it in O(n log k) or O(n) average.
How to spot a sorting question
Sorting is rarely the answer by itself; it's the step that makes the rest easy. These clues point to it, and to the chapters of this course:
Intervals, meetings, schedules, overlaps → sort by start (or end) time, then scan once. Pattern 1: sort first, then scan.
Duplicates, closest values, minimum difference, h-index → sort, then compare neighbours or positions. Pattern 1.
An unusual order — by frequency, by another array, the largest number formed → a custom comparator. Pattern 2.
Values in a small range, or sort into two groups → counting or partitioning, in O(n). Pattern 3.
Merge two sorted arrays or lists, sort a linked list, count pairs `i < j` that are out of order → the merge step of merge sort. Pattern 4.
The input is already sorted → don't sort — use binary search or two pointers (see the Searching course).
And always check the constraints: n up to about 10⁴ allows O(n²); up to 10⁵–10⁶ needs O(n log n) — which is exactly what sorting costs — or better.
Key takeaways
Insertion sort for small or nearly sorted input; merge sort for stable or guaranteed; quick sort for raw speed; counting and radix for small integer keys.
Built-in sorts are hybrids (Timsort, introsort) — know whether yours is stable.
In interviews, sorting is usually the first step: sort, then scan, compare neighbours, or merge.
