A recursive parallel sort splits an array in half, sorts both halves concurrently, and then merges the two sorted halves with an ordinary sequential merge. Even on a machine with many idle cores the speedup flattens out. How do you reason about the ceiling, and how would you restructure the decomposition to raise it?

## Reasoning tool: work and span A fork-join computation is a directed acyclic graph of operations: forks branch it, joins rejoin it. Two numbers characterize it. - **Work (T1)**: the total number of operations - the time on one worker. - **Span (T-infinity)**, also called depth or critical path: the length of the longest chain of operations where each must finish before the next begins - the time on infinitely many workers. The best possible speedup is **T1 / T-infinity**, the *parallelism* of the algorithm. It is a property of the decomposition, not of the machine. If parallelism is 8, buying a 64-core machine buys you nothing past 8. This is why 'the cores are idle' is not evidence that the runtime is at fault - it may simply be that the graph has no more independent work at that moment. ## Applying it to the sort Split the array, sort halves concurrently, merge sequentially. - **Work**: the recurrence is W(n) = 2 W(n/2) + O(n), giving the familiar O(n log n). Parallelizing does not change the work, and should not - an algorithm that does far more total work to gain parallelism often loses on real machines. - **Span**: the two recursive sorts run concurrently, so only one contributes; then the merge is added. S(n) = S(n/2) + O(n). That expands to n + n/2 + n/4 + ... = O(n). The merge chain is linear. So parallelism = O(n log n) / O(n) = O(log n). For a million elements that is about 20 - meaning speedup saturates around twenty-fold no matter how many cores you own, and in practice much lower once overheads count. The last merge alone reads and writes every element with no internal parallelism; it is a hard floor. ## Where the intuition usually goes wrong People notice that the *sorting* is fully parallel and conclude the whole thing is. But a chain is only as short as its longest link, and the combine steps of a divide-and-conquer algorithm sit on the critical path exactly like the split steps do. Whenever the combine is sequential and linear in the subproblem size, it dominates the span. This generalizes into a design rule: **in divide-and-conquer, the combine step determines your scalability ceiling.** Parallel sum has an O(1) combine (one addition), so its span is O(log n) and its parallelism is O(n / log n) - excellent. Parallel sort has an O(n) combine, and pays for it. ## Restructuring: parallelize the merge The standard fix makes merging itself divide-and-conquer: ``` parallelMerge(A, B, out): if small: sequentialMerge(A, B, out); return pick the median element m of the longer run, at index i j = binarySearch(m, shorter run) // O(log n) place m at position i + j in out fork parallelMerge(A[..i], B[..j], out[..i+j]) parallelMerge(A[i+1..], B[j..], out[i+j+1..]) join ``` Each level does an O(log n) binary search and splits both inputs, so merge span becomes O(log^2 n) instead of O(n). Plugging that into S(n) = S(n/2) + O(log^2 n) gives a total span of O(log^3 n) and parallelism close to n / log^2 n - now the machine, not the algorithm, is the limit. The price: extra work for the searches, an out-of-place output buffer, and considerably harder code. ## Other decomposition levers - **Change the algorithm, not just the merge.** A sample-sort or bucket-based approach partitions once by value ranges, sorts buckets fully independently, and then only concatenates - a trivial combine. It moves the hard part into choosing good splitters, which can be done by sampling. - **Overlap combine with compute.** Merge pairs as soon as both are ready rather than waiting for a whole level, so the graph is not artificially level-synchronized. - **Reduce constants where the span lives.** The final merge is memory-bandwidth bound; a cache-friendly layout speeds up the exact step that dominates. ## How to decide in practice Do the span analysis before writing code: if the combine is O(size), expect logarithmic parallelism and do not promise linear scaling. Then measure: plot speedup against worker count and find where the curve flattens. If it flattens far below core count while CPU is idle, you are span-bound and no amount of scheduler tuning will help - the decomposition must change. If instead workers are busy but speedup is poor, you are overhead- or memory-bound, a different problem with different fixes. The principal-level point is that scalability is designed in at decomposition time. Choosing an algorithm whose combine step is cheap is worth far more than any amount of tuning applied afterwards.