Why does sorting the weights first make heaviest-with-lightest pairing a safe greedy move under a per-load cap?

## Sorting as the step that creates the greedy order A very large share of correct greedy algorithms have the same two-part shape: **sort by the right key, then make one linear pass**. It is tempting to read the sort as housekeeping — tidying the input before the real work. It is the opposite. The pass is usually trivial; the sort is where the design decision lives, because ordering by the correct key is what puts the provably safe candidate at a known position, so the pass can simply take it. Say a ferry carries at most **two** passengers per boat under a per-boat weight cap, and you want to minimise boats. Sorted ascending, the rule is: look at the heaviest remaining and the lightest remaining; if they fit together, send both; otherwise send the heaviest alone. ``` // w[0..n-1] sorted ascending; cap = per-boat weight limit lo = 0 hi = length(w) - 1 boats = 0 while lo <= hi: if w[lo] + w[hi] <= cap: lo = lo + 1 hi = hi - 1 boats = boats + 1 ``` ## The safe-move argument The heaviest remaining passenger, call them H, has to board *some* boat in every possible solution — nobody is left behind. So the boat carrying H is not optional; the only freedom is whether it carries a second person. Now consider the lightest remaining, L. - If `w[L] + w[H] > cap`, then no remaining passenger fits with H, because everyone else weighs at least as much as L. H sails alone in every solution, and doing so immediately costs nothing. - If `w[L] + w[H] <= cap`, pairing them is safe. Suppose some optimal plan instead puts H with someone else, or alone, and puts L elsewhere. Moving L into H's boat and leaving L's former companion (if any) where they were never increases the boat count, because whoever was with H was at least as heavy as L and so still fits wherever they end up. There is therefore an optimal plan that pairs H with L — the greedy-choice property, stated for this rule. After the boat departs, what remains is the same problem on a strictly smaller passenger list: optimal substructure closes the recursion. The two-pointer loop is exactly this argument applied repeatedly. ## What the sort actually contributes Three things, none of them cosmetic. 1. **It names the candidates.** "Heaviest" and "lightest" are positions `hi` and `lo` only because the sequence is ordered. On unsorted input, applying the rule at all would mean scanning for both extremes every step. 2. **It makes the argument possible.** The proof leans on *everyone else weighs at least as much as the lightest*. That is a consequence of the ordering, not of the data. 3. **It fixes the cost profile.** The scan is linear and each step is constant work, so ordering the input dominates the running time — the greedy pass is the cheap half. And the key must be right. Sorting ascending and then pairing *adjacent* passengers is also a rule over sorted data, and it is wrong. With a cap of 10 and weights 3, 5, 5, 7: adjacent pairing sends (3,5) together, then finds 5+7 = 12 over the cap and needs two more boats — **three** in total. Opposite-ends pairing sends (3,7) = 10 and then (5,5) = 10 — **two**. Same sorted array, same greedy discipline, different key, different answer. "I sorted it" is not an argument; "I sorted by the key that puts the safe candidate at a known end" is. ## Where the argument stops The safety proof used the at-most-two constraint in an essential way: H needs *at most one* companion, so "the best companion" is a single well-defined choice. Raise the capacity to three or more per boat and the choice becomes a combination rather than a candidate, the substitution argument no longer goes through, and this rule loses its guarantee. Notice how narrow the licence is — a correct greedy is correct for the exact problem you argued, and a small-looking change to the constraints can quietly turn it into a heuristic. A related practical limit: if items arrive as a stream you cannot buffer, you cannot sort, and without the order there is no greedy order to exploit. You either buffer and sort, or accept an online rule with no optimality claim.