← Learn DSA · Lesson 5 of 11
Sorting
Usually not the answer, but very often the step that makes the answer easy.
The idea
You will almost never write a sort in an interview. You will constantly decide to sort, and that decision is the actual skill.
Sorting costs O(n log n). The question is always whether it buys you more than it costs. It usually does, because a sorted array unlocks techniques that are otherwise unavailable: binary search becomes possible, two pointers from both ends becomes meaningful, duplicates become adjacent, and "closest pair" becomes "neighbours".
The comparison sorts worth knowing by shape rather than by code:
- Insertion sort — O(n²), but O(n) on nearly-sorted input and stable. This is what production sorts fall back to for small runs, and it is the one animated below because every move is visible.
- Merge sort — O(n log n) guaranteed, stable, needs O(n) extra space. The one to reach for when worst case matters or stability is required.
- Quicksort — O(n log n) expected, O(n²) worst, in place. Fastest in practice; the worst case is real but rare with a randomised pivot.
- Heapsort — O(n log n) guaranteed and in place, but not stable and slower in practice than quicksort.
Stability — equal elements keeping their original order — matters more often than people expect. Sorting by one field then another only works if the second sort is stable.
And when the keys are small integers, comparison is not required at all: counting sort is O(n + k), which beats the O(n log n) lower bound because it never compares anything.
Walkthrough
Insertion sort: each element is lifted out and the larger ones shuffle right to make room. The left of the array is always sorted — watch that boundary move.
What it costs
- time
- O(n log n) for any comparison sort; O(n + k) for counting sort
- space
- O(1) for quicksort and heapsort, O(n) for merge sort
The O(n log n) bound applies only to sorts that compare. Counting and radix sorts beat it by not comparing at all, which is available whenever the keys are small integers.
When to reach for it
- Sorting makes the real algorithm obvious — binary search, two pointers, or a sweep.
- You need the k largest or smallest and k is close to n. Below that, a heap is cheaper.
- Duplicates or near-duplicates need to be found, and sorting puts them next to each other.
- The problem is about intervals, which almost always begins with sorting by start or end.
Rather than the obvious alternative
A hash map
If you only need counts or membership, hashing is O(n) and sorting is O(n log n). Sorting earns its cost when you need *order* — the nearest value, the k-th, a range — which a hash map cannot give you.
A heap
For "top k out of n", a heap is O(n log k) against sorting's O(n log n). When k is 10 and n is ten million, that is the whole solution.
Quickselect
If you need only the k-th element and not the order of everything else, quickselect averages O(n). Sorting to find one element does far more work than asked.
How to spot it
- The problem mentions "sorted" in the input, or the answer is easier if you assume it.
- You are looking for pairs, duplicates, or the closest values.
- It is an interval problem — sort by start or end almost always comes first.
- A brute force compares every element with every other, and order would let you stop early.
Where it goes wrong
Default comparators on numbers
JavaScript's `.sort()` compares as strings by default, so `[10, 9, 1]` sorts to `[1, 10, 9]`. Always pass `(a, b) => a - b`.
Sorting when you only needed counts
Reaching for a sort out of habit turns an O(n) hash pass into O(n log n). Ask what the order is actually buying before paying for it.
Assuming stability
Not every language guarantees a stable sort. If a second sort must preserve the first, check — or sort once on a composite key.
Sorting a copy you then throw away
Sorting in place mutates the caller's array. In an interview, say which you are doing; in real code, it is a genuine source of bugs.
Try it
Two short checks. They run the same way the practice problems do — write the function, press Run.
Return true if nums is in non-decreasing order. One pass, no sorting.
Tests
5 cases, 2 hidden| call | type | expected | result |
|---|---|---|---|
| isSorted([1,2,2,5]) | sorted | true | — |
| isSorted([1,3,2]) | not sorted | false | — |
| isSorted([7]) | single element | true | — |
| withheld | hidden | withheld | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Hints
Stuck? Hints open one at a time, each giving a little more away.
2 hints left
Practise it
- Sort Colorsmedium
Build it
The problems above are one function each. These assemble the same ideas into a working thing across several files.