Sorting-Based Patterns

This one is less a single algorithm than a habit, and it might be the highest-leverage habit in the whole catalog: before you do anything clever, ask whether sorting the input first would make the problem fall apart in your hands. A startling number of problems that look quadratic and tangled become a single linear walk the moment the data is in the right order. Sorting is not the solution; it is the setup that makes an easy solution possible.

The reason it works is that sorting manufactures a guarantee. Unordered data forces you to consider every element against every other, because anything could relate to anything. Ordered data lets you assume everything before the current position is already handled, and that assumption is what collapses the search.

The habit: sort, then the answer is a walk

Take scheduling a batch of jobs on one machine to minimize the total time everyone spends waiting. Brute-forcing the best order is factorial. But there is a clean truth hiding here: if a long job goes first, it makes everyone behind it wait longer, so the shortest jobs belong at the front. Sort by duration, and the optimal order is simply the sorted order.

def total_waiting_time(durations):
    durations.sort()                 # shortest first
    waited = 0
    elapsed = 0
    for d in durations:
        waited += elapsed            # this job waited for everything before it
        elapsed += d
    return waited

The sort does the real work; the loop is a bookkeeping pass that just reads off the answer. This is the shape over and over: the insight is which key to sort by, and once that is right, a greedy or two-pointer sweep finishes the job in linear time. Choosing the key is the actual skill, and it is where the thinking lives.

In the wild: how many rooms does the day need?

A real scheduler has to answer a sharper question: given all of today's meetings, what is the greatest number happening at once? That number is exactly how many rooms, or servers, or database connections you must provision. Comparing every meeting to every other is O(n^2), but sorting turns it into a sweep. Pull the start times and end times into two sorted lists and walk them together: every time the next event is a start, a room is claimed; every time it is an end, one is released. The high-water mark is your answer.

def rooms_needed(meetings):
    starts = sorted(s for s, e in meetings)
    ends = sorted(e for s, e in meetings)
    rooms = peak = 0
    i = j = 0
    while i < len(starts):
        if starts[i] < ends[j]:      # a meeting begins before the next one ends
            rooms += 1
            peak = max(peak, rooms)
            i += 1
        else:                        # a meeting ended, reclaim its room
            rooms -= 1
            j += 1
    return peak

It is the same move as the waiting-time toy, one level up: sorting imposes a timeline, and once events are in chronological order, a single pass reads off a fact that looked global. The problem never changed shape; sorting just revealed the shape it already had. This sweep-line idea, sort the events and walk the timeline, is one of the most reused tricks in scheduling, geometry, and capacity planning.

Four meetings 1-5, 2-6, 4-8 and 7-9 drawn as bars on a timeline; a sweep line finds the moment three overlap at once (1-5, 2-6 and 4-8 around time five), so the day needs three rooms, a peak read off in one sorted pass instead of comparing every pair.

The trigger

The problem mentions order, ranking, overlaps, gaps, "closest," or "at most one at a time," and the brute force compares elements pairwise. That pairwise comparison is the tell: sorting almost always turns it into a neighbors-only scan. When stuck, one of the first questions to try is simply, "what if this were sorted, and by what?"

Where it shows up

  • Scheduling and greedy selection: shortest-job-first, activity selection, deadline ordering.
  • Interval work: sorting by start is the mandatory first step of Merge Intervals and sweep-line problems.
  • Finding structure: closest pair of values, largest gap, grouping anagrams by their sorted letters, deduplicating by bringing equals next to each other.

Where it bites

The entire solution rests on the sort key, and the wrong key produces confident nonsense: sorting meetings by start when the greedy argument needed end time, for instance, quietly gives wrong answers on valid input. And sorting is not free. At O(n log n) it can be the bottleneck, and if the data is already ordered or nearly so, or the values are small integers, a linear counting or bucket approach may beat it.

When it is the wrong tool

Sorting is overkill when you do not actually need global order. If the question is "the k largest," a heap answers it in O(n log k) without sorting the whole array, and if it is "the single largest," a linear scan is both faster and simpler. Sorting also destroys the original order, so if positions or arrival sequence carry meaning, sorting in place throws away information you needed; sort indices or a copy instead. And on truly massive or streaming data where a full sort will not fit in memory, reach for external sorting or a streaming sketch rather than assuming sort() is available.

Its neighbors

Sorting is the runway for a lot of other patterns. It is the required first step of Merge Intervals, the enabler that makes most Greedy proofs go through, and the precondition that lets Two Pointers and Binary Search work at all. Think of it less as a pattern you finish with and more as the one you start with.

References