Implement a parallelized sort

Problem Statement

Implement a parallelized version of the Merge Sort algorithm. Your task is to sort an array of integers using multiple threads to process subarrays concurrently.

Given a large array, the algorithm should recursively split the array into halves until a certain threshold is reached, at which point it should perform a sequential sort (or continue parallelizing if resources allow). Use a thread pool or a similar mechanism to manage concurrent execution, ensuring the system does not spawn an unbounded number of threads.

Function Signature

# You may use a thread pool or standard threading library
def parallel_merge_sort(arr: list[int], max_threads: int) -> list[int]:
    """
    Sorts the array in-place or returns a sorted version.
    'max_threads' is a hint for the concurrency limit.
    """
    pass

Requirements

1. Workload Partitioning: Decide how to divide work effectively to minimize overhead.
2. Thresholding: Implement a mechanism to switch from parallel processing to sequential processing for small subarrays to avoid the overhead of thread creation.
3. Synchronization: Ensure the final merged results are correctly ordered.

Examples

Example 1: Input: arr = [5, 2, 9, 1, 5, 6], max_threads = 2 Output: [1, 2, 5, 5, 6, 9]

Example 2: Input: arr = [10, -1, 3, 0], max_threads = 4 Output: [-1, 0, 3, 10]

Constraints

• Array length: 1 to 10^6.
• Value range: -10^9 to 10^9.
• The algorithm should perform significantly better than sequential Merge Sort on large arrays given sufficient hardware.