Sort a Large Array Using Multiple Threads

You are given a large array of integers nums and a thread count k. Sort the array in ascending order using multiple threads, structured as follows:

1. Partition the array into k contiguous chunks of (nearly) equal size.
2. Sort each chunk concurrently, one worker thread per chunk, using your language's real threading primitives (e.g., threading.Thread in Python, std::thread in C++, Thread/ExecutorService in Java). Each thread may use any standard comparison sort on its own chunk.
3. Merge the k sorted chunks into one fully sorted array. The merge must not simply re-sort the concatenated data: it must exploit the fact that the chunks are already sorted. The intended approach is a k-way merge using a min-heap (priority queue), which merges n total elements across k sorted runs in O(n log k) time.

Return (or print, per the judge's I/O format) the fully sorted array.

Requirements

• The k chunk sorts must actually run on separate threads; the main thread must wait for all workers to finish before merging.
• The final result must be deterministic and correct regardless of thread scheduling order. Threads must not write to shared state without clear ownership (each worker should own exactly its chunk).
• Target overall work: O(n log n) total sorting work split across threads, plus an O(n log k) merge.
• Handle edge cases: k greater than the array length, an empty array, and arrays with duplicate values.

Example

nums = [5, 2, 9, 1, 7, 3], k = 2

Chunks: [5, 2, 9] [1, 7, 3]
After parallel
chunk sorts: [2, 5, 9] [1, 3, 7]
k-way merge: [1, 2, 3, 5, 7, 9]

Output: [1, 2, 3, 5, 7, 9]

Constraints

• 0 <= n <= 10^6 elements, each in the signed 32-bit integer range.
• 1 <= k <= 16.
• Duplicates are allowed and must all appear in the output.