Free lesson · Concurrency Interview Mastery

Exercise: Multi-threaded Merge Sort

Hard5 min readconcurrencymultithreadinginterview-prep

This exercise builds the fork-join merge sort, reasons about the sequential threshold, and diagnoses the no-threshold and join-ordering bugs. Reason each through before the solution - the goal is to parallelize divide-and-conquer correctly and to understand why the threshold is the critical performance lever.

Important: Two anchors: fork one half and compute the other in the current thread, joining before the merge (the merge needs both halves fully sorted), and below a sequential threshold, sort sequentially (forking to size-1 drowns in task-creation overhead).

Part 1 - Fork-join merge sort

Your task: Implement a parallel merge sort with fork-join, a sequential threshold, and the fork-one/compute-other optimization.

parallelMergeSort(a, lo, hi): if hi - lo <= THRESHOLD: sequentialSort(a, lo, hi); return. Else: mid = (lo+hi)/2; leftTask = fork(() -> parallelMergeSort(a, lo, mid)); parallelMergeSort(a, mid, hi) (this thread); join(leftTask); merge(a, lo, mid, hi). Fork the left, compute the right in-place, join, merge. </details>

Part 2 - The sequential threshold

Your task: Explain why the sequential threshold matters and what goes wrong without it.

Without a threshold, the recursion forks all the way to size-1 subarrays - ~2n tasks for n elements. Each fork has overhead (task allocation, scheduling, join synchronization), which for tiny subarrays dwarfs the actual sorting work - so the parallel version is slower than sequential (and may exhaust memory/stack). The threshold caps tasks at ~n/THRESHOLD, making overhead negligible; below it, a sequential sort does the small work efficiently. Fork only until subtasks are big enough that parallelism gain > fork overhead. </details>

Part 3 - Find the bugs

// Bug A - no threshold:
function parallelMergeSort(a, lo, hi):
    if hi - lo <= 1: return                     // <-- forks to size 1
    mid = (lo + hi) / 2
    leftTask  = fork(() -> parallelMergeSort(a, lo, mid))
    rightTask = fork(() -> parallelMergeSort(a, mid, hi))   // <-- forks BOTH
    join(leftTask); join(rightTask)
    merge(a, lo, mid, hi)

// Bug B - merge before join:
    leftTask = fork(() -> parallelMergeSort(a, lo, mid))
    parallelMergeSort(a, mid, hi)
    merge(a, lo, mid, hi)                        // <-- merge WITHOUT joining left
    join(leftTask)

Your task: Identify the performance bug in A and the correctness bug in B.

Bug A: two problems - (1) no threshold, so it forks to size-1 (massive task overhead, far slower than sequential); (2) forking both halves wastes the current thread (it just waits on two forks instead of doing one half itself). Fix: add a threshold, and fork one half while computing the other in-place. Bug B: merge runs before join(leftTask), so it merges while the left half may still be being sorted on another thread - merging partially-sorted (or concurrently-mutated) data → incorrect result and a data race. Fix: join(leftTask) before merge - both halves must be fully sorted before merging. </details>

Solution

Part 1 - Fork-join merge sort

THRESHOLD = 2048

function parallelMergeSort(a, lo, hi):
    if hi - lo <= THRESHOLD:
        sequentialSort(a, lo, hi)               # small -> sequential, no forking
        return
    mid = (lo + hi) / 2
    leftTask = fork(() -> parallelMergeSort(a, lo, mid))    # FORK left half
    parallelMergeSort(a, mid, hi)                          # compute right in THIS thread
    join(leftTask)                                          # WAIT for left
    merge(a, lo, mid, hi)                                   # combine sorted halves

The two recursive sorts touch disjoint regions ([lo,mid) and [mid,hi)), so they're independent and parallelizable. We fork one (left) and compute the other (right) in the current thread - so the current thread does useful work rather than idling, halving the task count. We join (wait for the forked left) before merging, because the merge reads both fully-sorted halves. Below THRESHOLD, we sort sequentially to avoid fork overhead on small subarrays.

Part 2 - The sequential threshold

Without a threshold, the recursion forks down to size-1 subarrays, creating roughly 2n tasks for an n-element array. Each fork costs: allocating a task object, pushing it to a work-stealing deque, scheduling it, and synchronizing on join. For a 2-element subarray, that overhead is orders of magnitude more than the single comparison the sort actually does - so the "parallel" version spends almost all its time on task bookkeeping and runs slower than a plain sequential sort (and can exhaust memory or stack with millions of tiny tasks). The threshold fixes this by capping tasks at ~n/THRESHOLD: above the threshold, forking exposes parallelism; below it, a sequential sort does the small work with zero task overhead. The principle is universal to parallel divide-and-conquer: fork only until subtasks are large enough that the parallelism gain exceeds the fork overhead, then switch to sequential. The threshold value is tuned empirically (depends on per-element work and fork cost), typically a few hundred to a few thousand elements.

Part 3 - The bugs

Bug A - no threshold + double fork. Two compounding problems. (1) No threshold: the base case is hi - lo <= 1, so it forks all the way to size-1 subarrays - ~2n tasks, each with fork overhead vastly exceeding its tiny workload. The result is slower than sequential sorting, defeating the entire purpose. (2) Forking both halves: it forks both the left and right subtasks and then just joins both - so the current thread does no sorting work itself, it only waits. This doubles the task count and wastes the current thread. The fix is both: add a sequential threshold (sort sequentially below it), and fork one half while computing the other in the current thread. The combination - threshold plus fork-one-compute-other - is what makes fork-join efficient.

Bug B - merge before join. The code calls merge(a, lo, mid, hi) before join(leftTask). The left half is being sorted on a forked task that may not have finished, so the merge reads a left half that's partially sorted (or being mutated concurrently) - producing an incorrect (unsorted) result, and a data race (the merge reads the left region while the forked task writes it). The merge has a hard dependency on both halves being fully sorted, which join enforces. The fix is to join(leftTask) before merge: wait for the forked left sort to complete, so both halves are fully sorted, then merge. This is the fundamental fork-join discipline - join before consuming a forked task's result. Forgetting the join (or ordering it after the consumer) is the classic fork-join correctness bug.

Both bugs reinforce the design: threshold + fork-one-compute-other for performance (Bug A), and join-before-merge for correctness (Bug B).

Common mistakes

Warning: Watch for: (1) No sequential threshold - fork-to-size-1 drowns in task overhead (slower than sequential); add a threshold. (2) Forking both halves - wastes the current thread; fork one, compute the other in-place. (3) Merging before joining - merges partially-sorted data (race + wrong result); join first. (4) Threshold too high - too few tasks to fill all cores (under-parallelized). (5) Manual thread-per-subarray - no load balancing, high overhead; use a work-stealing pool. (6) Forgetting the merge needs aux space - allocate or reuse an auxiliary array.

Why this exercise matters for interviews

Interview: Parallel merge sort is the classic fork-join interview question. Part 1 (fork-join with threshold) is the expected design - fork one half, compute the other, join, merge, with a sequential cutoff. Part 2 (the threshold) tests the key performance insight: forking to size-1 is catastrophic, so go sequential below a threshold. Part 3 (bugs) targets the signature performance error (no threshold + double fork) and the signature correctness error (merge before join). The throughline interviewers reward: fork-join for independent halves, the sequential threshold as the critical lever, fork-one-compute-other, work-stealing for load balancing, and the sequential merge as the speedup ceiling (Amdahl). The threshold reasoning and the join-before-merge discipline are what most distinguish a strong answer.

Back to Concurrency Interview Mastery