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

Implement the ParallelMergeSorter class:

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