Learn key sorting algorithms, when to use each, and how sorting unlocks other patterns.
Sorting arranges elements in a defined order. In interviews you rarely implement sorting from scratch — you use the language built-in sort (O(n log n)). But understanding how sorting works helps you choose the right approach, reason about stability, and know when sorting is the first step to solving a harder problem.
Comparison sorts O(n log n) lower bound · Non-comparison O(n)
Merge Sort O(n) · Quick/Heap O(log n) stack · Counting O(k)
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
O(n²) — repeatedly swap adjacent elements; simple but slow
O(n²) — find min and place it; not stable
O(n²) worst, O(n) best — good for nearly sorted data
O(n log n) — divide and conquer; stable; uses O(n) extra space
O(n log n) avg, O(n²) worst — in-place; fastest in practice
O(n log n) — uses a heap; in-place but not stable
O(n) — works on integers in a range
equal elements preserve their original order (Merge Sort is stable)
always prefer language built-ins in interviews unless asked otherwise