the combine step

After your friends hand back their two sorted half-piles of forms, you still have work to do: you must weave the two sorted piles into one. That weaving is the combine step — the part of a divide-and-conquer algorithm that takes the already-solved subproblem answers and assembles the answer to the whole problem. The divide and conquer steps get the headlines, but the combine step is usually where the cleverness and most of the running-time budget live.

Mechanically, combine runs after the recursive calls return. In merge sort it is the Merge routine: walk a finger along each sorted half, repeatedly copy the smaller front element into the output, and you produce a fully sorted array in O(n) time and one linear pass. In the maximum-subarray algorithm the combine step is the clever part — it scans outward from the split point to find the best subarray that straddles the boundary, the one case the two recursive answers cannot see. In Karatsuba multiplication, combine adds and shifts three smaller products. The cost of this step is exactly the f(n) term in the recurrence T(n) = a T(n/b) + f(n), so it controls how fast the whole algorithm runs.

The combine step is where you should focus your design effort, because the overall speed often hinges on making it cheap. The Master Theorem makes this concrete: with T(n) = 2 T(n/2) + f(n), a linear combine f(n) = O(n) gives O(n log n), but a quadratic combine f(n) = O(n^2) gives O(n^2) and wipes out the benefit of dividing. A common beginner mistake is to write a slow combine — for instance using a nested loop to merge two sorted lists in O(n^2) instead of the O(n) two-finger merge — silently turning an n log n algorithm into an n^2 one.