The Price of Order

Sorting as preparation

Ask any experienced engineer how to find duplicates in an array, and the first answer will usually be "sort it first". Ask how to find the median, and again: sort first. Range queries? Sort first. This is not laziness, it's a legitimate design pattern. Many O(n²) brute-force algorithms collapse to O(n log n) once the input is sorted, because sortedness enables the two-pointer, sliding-window, and binary-search patterns that follow.

The implication is that learning to sort isn't really learning an algorithm. It's learning to recognise the shape of problems that sorting unlocks. The algorithm itself is in sorted() or Arrays.sort(), and re-implementing it is rarely productive outside a classroom.

Comparison sorts, briefly

Every comparison-based sort is some way of asking "which of these two elements is larger?" and rearranging accordingly. The three that matter in practice are merge sort (O(n log n), stable, O(n) extra memory), quicksort (O(n log n) expected, O(n²) worst-case, in-place), and heapsort (O(n log n) worst-case, in-place, not stable). Most standard libraries use an adaptive hybrid (Python's Timsort, C++'s introsort, Java's dual-pivot quicksort) tuned for the partially-sorted data that appears in practice.

The O(n log n) lower bound for comparison sorts is genuinely a lower bound, not a limit of current knowledge. The proof is a counting argument: there are n! possible permutations, each comparison splits the space into two halves, and a decision tree distinguishing n! cases needs depth at least log(n!) = Θ(n log n). No amount of cleverness bypasses this if your only operation is pairwise comparison.

Non-comparison sorts

But comparison is not the only operation. If you know the keys are integers in a small range, you can sort in O(n) with counting sort: count the occurrences of each value, then emit them in order. If the keys are integers of bounded width, radix sort runs in O(n·w) where w is the number of digits, effectively O(n) for fixed-width integers. These are not faster algorithms of the same problem; they are the same algorithm applied to a different problem (one with structural information beyond "we can compare").

def counting_sort(a, k):
    # a: non-negative ints in [0, k]
    counts = [0] * (k + 1)
    for x in a: counts[x] += 1
    out, idx = [0] * len(a), 0
    for v, c in enumerate(counts):
        for _ in range(c):
            out[idx] = v; idx += 1
    return out

Counting sort is particularly useful inside more sophisticated algorithms, bucket sort, suffix array construction, Dutch national flag. It is almost never the end product of your code, but it is often a phase of something larger.

Binary search, the doubling game in reverse

Given a sorted array and a target value, binary search finds the target in O(log n) by repeatedly halving the search space. The algorithm is a three-liner; the subtlety is in the off-by-one decisions at the boundary.

def lower_bound(a, target):
    # Smallest index i such that a[i] >= target.
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < target: lo = mid + 1
        else:               hi = mid
    return lo

The half-open interval [lo, hi) is the key to writing this without bugs. hi starts at len(a), not len(a) - 1, because the answer might be "past the end". hi = mid (not hi = mid - 1) because a[mid] is a valid candidate when a[mid] >= target. lo = mid + 1 because a[mid] is not a candidate when a[mid] < target. Every correct binary-search variant reduces to getting these three decisions consistent.

Binary search on the answer

The most powerful technique in this module. Many problems ask "what is the minimum (or maximum) X such that some condition holds?" If the condition is monotone (true for X, and for all X' larger than X) you can binary-search on X itself. The structure:

def min_feasible_answer(lo, hi, feasible):
    # feasible(x) is monotone: if feasible(x), then feasible(x') for all x' >= x.
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid): hi = mid
        else:              lo = mid + 1
    return lo

Concrete example: "given n boards and k painters, what is the minimum time to paint all boards if each painter works on a contiguous range?" The answer is between max(boards) and sum(boards). The predicate "can we paint everything in time T?" is monotone in T and checkable in O(n) by greedy assignment. Binary-searching T gives O(n log(sum−max)) total, vastly better than trying every possible T.

Quickselect, the median shortcut

When you need the k-th smallest element but not the whole sorted order, you do not need to sort. Quickselect is quicksort's partition step without the recursion into the other half. O(n) expected, O(n²) worst-case. The nth_element family in C++ and heapq.nsmallest-for-small-k in Python both rely on this idea.

Stability

A sort is stable if equal elements keep their relative order. This matters when you sort by one field and want to preserve the ordering by another, for example, sorting a list of students by grade while preserving alphabetical order within each grade. Merge sort is stable; heapsort is not; quicksort's stability depends on implementation. Python's Timsort and Java's Arrays.sort for objects are stable by contract; Arrays.sort for primitives in Java is not, because it uses quicksort.

Complexity summary

When to sort, when not to

Sort when the downstream algorithm benefits from sorted input, two pointers, sliding window over a sorted view, median finding. Do not sort just to find a maximum or a sum, those are O(n) operations on unsorted input. Do not sort when a hash map solves the problem in one pass, checking for duplicates, counting occurrences, two-sum on unsorted data. Sorting is a tool, not a habit.

Where beginners go wrong

• Implementing a sort for a real problem. Almost always, the standard library does it faster and more correctly. Use sorted.
• Off-by-one in binary search. The inclusive/exclusive boundary is not interchangeable. Pick one convention (half-open [lo, hi) is the most robust) and stick with it.
• Forgetting that quicksort is not stable. If you sort by a secondary key first and then a primary key, the secondary ordering is only preserved if both sorts are stable.
• Binary-searching a non-monotone predicate. The algorithm is only correct when the boundary between feasible and infeasible is a single flip.

What to read next

Continue with the final module, Two Pointers & Sliding Window, which operate almost exclusively on sorted arrays, and which are the real reason you wanted the array sorted in the first place.