Why sorting matters

Sorting is not a goal in itself. It is a precondition that makes other algorithms possible or faster. In competitive programming and production engineering alike, "sort first" is often the first move you consider.

What sorted data buys you

Binary search. An unsorted array requires a linear scan — O(n) — to find a value. Once sorted, binary search cuts the search space in half on every step — O(log n). At n = 1 000 000 that is about 20 comparisons instead of a million.

Two-pointer technique. Many problems that look like nested loops can be solved in O(n) once the data is sorted. To find whether any two numbers sum to a target, place one pointer at the start and one at the end. If their sum is too large, move the right pointer left; too small, move the left pointer right. Because the array is sorted, each pointer only moves in one direction — O(n) total. Without sorting you need an O(n²) brute-force search or an O(n) hash set lookup.

Deduplication. In a sorted sequence, duplicates are adjacent. A single linear scan can skip them — O(n) with O(1) extra space. On unsorted data you need an O(n) hash set just to detect duplicates, with the associated memory cost.

Median and order statistics. The median of a sorted list is the middle element — O(1) to read once sorted. Range queries ("all values between 10 and 50") become a binary-search pair — O(log n) to find the boundaries, then read the slice.

Merge. Two sorted sequences merge into one sorted sequence in O(n + m) time — just advance two pointers and always take the smaller. Merging unsorted sequences requires sorting first.

The comparison-based lower bound

No algorithm that works by comparing pairs of elements can sort n items in fewer than O(n log n) comparisons in the worst case. This is not a limitation of known algorithms — it is proven mathematically.

The argument: sorting n items means choosing one of n! possible orderings. Each comparison is a yes/no question that rules out at most half the remaining possibilities. To distinguish n! outcomes you need at least log₂(n!) questions. By Stirling's approximation, log₂(n!) = Θ(n log n). So n log n comparisons are necessary, not just sufficient.

Algorithms like radix sort and counting sort sidestep this bound because they do not compare elements directly — they exploit structure in the keys. For general data (arbitrary objects with a < operator), O(n log n) is the floor.

Sorting as a preprocessing step

The cost of sorting is O(n log n). If it enables subsequent operations that would otherwise each cost O(n) or O(n²), the sort pays for itself quickly.

• Sort once, binary-search k times: O(n log n + k log n) instead of O(kn).
• Sort once, find all pairs with two-pointer: O(n log n + n) instead of O(n²).
• Sort once, deduplicate: O(n log n + n) instead of O(n) with a hash set (no memory overhead).

When a problem involves "find a pair," "find the nearest value," "count distinct elements," or "process in order" — consider sorting first.

Where to go next

Next: merge sort — implementing the divide-and-conquer sort that achieves O(n log n) and timing it against insertion sort's O(n²) to make the difference tangible.