Overview
Sorting is rarely the whole problem, but it is the first step in an enormous number of solutions: once data is ordered, duplicates sit next to each other, two pointers become valid, intervals can be merged and binary search applies. Knowing the built-in sort is O(n log n) is often all you need — but interviews also test whether you understand how the classic algorithms work.
Comparison-based sorting cannot beat O(n log n) in the worst case. Merge sort guarantees it and is stable; quicksort is usually fastest in practice but degrades to O(n²) with bad pivots; heap sort uses O(1) extra space. When values come from a small range, counting sort and radix sort skip comparisons entirely and run in linear time.
Key concepts
Tick a concept once you can explain it in your own words without notes.
Complexity cheat sheet
| Operation | Cost |
|---|---|
| Bubble / insertion sort | O(n²); insertion is O(n) on nearly sorted data |
| Merge sort | O(n log n) time, O(n) space, stable |
| Quicksort | O(n log n) average, O(n²) worst |
| Heap sort | O(n log n) time, O(1) space |
| Counting sort | O(n + k) for values in a range of size k |
Patterns to recognise
Sort, then sweep
Use it for: Merging intervals, finding duplicates, greedy scheduling.
Sorting makes related items adjacent; a single pass finishes the job.
Custom order
Use it for: Largest number from digits, sort by frequency, relative order.
Write a comparator that encodes the desired order (and is a strict weak ordering).
Partial sorting
Use it for: k-th largest, top-k.
Quickselect (O(n) average) or a heap (O(n log k)) instead of a full sort.
Code template
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
merged, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= keeps the sort stable
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return merged
void mergeSort(vector<int>& a, int lo, int hi, vector<int>& tmp) { // sorts [lo, hi)
if (hi - lo <= 1) return;
int mid = lo + (hi - lo) / 2;
mergeSort(a, lo, mid, tmp);
mergeSort(a, mid, hi, tmp);
int i = lo, j = mid, k = lo;
while (i < mid && j < hi) tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
while (i < mid) tmp[k++] = a[i++];
while (j < hi) tmp[k++] = a[j++];
for (int t = lo; t < hi; ++t) a[t] = tmp[t];
}
void mergeSort(vector<int>& a) {
vector<int> tmp(a.size());
mergeSort(a, 0, (int)a.size(), tmp);
}
Common mistakes
- C++ comparators must return a < b, never a <= b — non-strict comparators cause undefined behaviour in std::sort.
- Quicksort with a fixed first/last pivot is O(n²) on already sorted input.
- Sorting loses original positions; keep the index alongside the value if you need it.
Quick check
Three questions on Sorting. Get all three right to earn +15 XP.
-
Which sort guarantees O(n log n) time even in the worst case?
Merge sort always splits in half. Quick sort can degrade to O(n^2) on bad pivots.
-
What does it mean for a sort to be stable?
Stability matters when you sort by one key after another.
-
Counting sort can beat O(n log n) because it:
It tallies values in O(n + k), where k is the range of the values.
Challenges
Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.
- Relative Sort ArrayLeetCode Easy +20
- Sort an ArrayLeetCode Medium +40
- Sort ListLeetCode Medium +40
- Largest NumberLeetCode Medium +40
- Sort Characters By FrequencyLeetCode Medium +40
- H-IndexLeetCode Medium +40
Stuck on Sorting?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor