AlgoMaster Logo

Design a Parallel Merge Sorter

medium9 min readUpdated August 31, 2026
Listen to this chapter
Unlock Audio

Design a reusable merge sorter that can process independent halves concurrently without creating an unbounded number of threads.

Implement the ParallelMergeSorter class:

  • ParallelMergeSorter(maxThreads) creates a sorter that may use at most maxThreads participating threads, including the thread that calls sort.
  • sort(values, onMerge) sorts values in nondecreasing order in place and returns only after the entire array is sorted.

Use merge sort: recursively divide each range into two halves, sort both halves, and merge them. When worker capacity is available, the two halves may be processed concurrently. When no capacity is available, continue sequentially in the current thread instead of waiting for another worker slot.

Call onMerge exactly once immediately before every merge operation. Because an array of length n requires n - 1 merges, a successful call must invoke it exactly max(0, n - 1) times. Merge callbacks for disjoint ranges may overlap when maxThreads > 1, but no more than maxThreads callbacks may be active simultaneously.

The callback is an observation hook used by the judge to verify real parallel progress and the worker limit. It returns normally and does not access or modify values.

The same sorter may be used for multiple completed calls, but the judge does not call sort concurrently on the same instance. Different sorter instances must be independent.

The judge supplies the arrays and callbacks. Standard concurrency, callback, collection, lock, and thread APIs are preloaded, so you do not need import, include, package, or using statements.

Example 1:

Input:

Output:

Explanation: Four elements form four one-element ranges. Combining them into one sorted range requires three merge operations.

Example 2:

Input:

Output:

Explanation: Duplicate and negative values are preserved. At most two participating threads may execute merge callbacks at once.

Constraints

  • 1 <= maxThreads <= 8
  • 0 <= values.length <= 100000
  • -10^9 <= values[i] <= 10^9
  • onMerge returns normally and does not access values.
  • The judge does not call sort concurrently on the same sorter instance.
  • Judge threads are not interrupted while waiting for workers.

Starter Code

Understanding the Problem

Merge sort naturally exposes parallel work. After splitting a range, the left and right halves do not overlap, so they can be sorted at the same time. The merge must wait until both halves are complete because it reads their final sorted contents.

Spawning at every recursive call is unsafe. An input of length n has O(n) recursive tasks, so unrestricted spawning can exhaust thread, memory, and scheduler resources. The sorter therefore needs a shared worker budget.

maxThreads counts the calling thread. A sorter with maxThreads = 1 is completely sequential. A sorter with maxThreads = 4 may reserve at most three additional worker slots.

Bounded Parallelism Strategy

Maintain maxThreads - 1 permits for additional workers. At a sufficiently large range:

  1. Try to reserve a permit without blocking.
  2. If successful, start one half on a new worker and sort the other half in the current thread.
  3. Wait for the worker to finish, then return its permit.
  4. If no permit is immediately available, sort both halves sequentially in the current thread.

The nonblocking permit attempt is important. A recursive worker must never hold part of the computation while waiting for another worker slot; it can always make progress sequentially instead.

A small parallel threshold avoids creating a new thread for tiny ranges where startup and scheduling cost would dominate the useful work. The threshold affects performance, not correctness or callback count.

Merge and Callback Ordering

Each recursive call owns a half-open range [left, right). Its child ranges are disjoint, so concurrent writes are safe.

After both children finish:

  1. Invoke onMerge exactly once.
  2. Merge the two sorted child ranges into temporary storage.
  3. Copy the merged values back into the original range.

Calling the hook before every merge makes concurrency observable without exposing internal worker objects. A length-zero or length-one range performs no merge and therefore invokes no callback.

Correctness

The base case contains at most one element and is already sorted.

For a larger range, assume both recursively processed halves are sorted. The merge repeatedly selects the smaller front element, so it produces a sorted range containing exactly the elements of both halves. By induction, the entire array is sorted and preserves every input value.

The parent joins its worker before merging, so it never reads an unfinished child range and sort cannot return early.

Every extra worker owns one permit. There are only maxThreads - 1 permits, so at most that many extra workers plus the caller can participate simultaneously. Falling back to sequential recursion ensures the worker budget cannot cause deadlock.

Code

Complexity Analysis

For an array of length n:

  • Time: O(n log n) total work. Parallel execution can reduce elapsed time for sufficiently large inputs, subject to scheduling overhead and the worker limit.
  • Auxiliary space: O(n) for merge buffers across disjoint active ranges, plus O(log n) recursion depth.
  • Callbacks: exactly max(0, n - 1) invocations.
  • Participating threads: at most maxThreads at any instant.