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

OperationCost
Bubble / insertion sortO(n²); insertion is O(n) on nearly sorted data
Merge sortO(n log n) time, O(n) space, stable
QuicksortO(n log n) average, O(n²) worst
Heap sortO(n log n) time, O(1) space
Counting sortO(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

Merge sort
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

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.

  1. Which sort guarantees O(n log n) time even in the worst case?

  2. What does it mean for a sort to be stable?

  3. Counting sort can beat O(n log n) because it:

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.

Stuck on Sorting?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor