Sort an array with k worker threads

Implement parallel_sort(nums: list[int], k: int) -> list[int], which returns every element of nums in ascending order and uses k worker threads for the heavy lifting.

Rules

• Split nums into contiguous segments, one per worker. Segment sizes may differ by at most one element.
• Workers run concurrently. A worker may read and write only the indices of its own segment.
• After all workers have finished, combine their results into the final sorted array. The combine step should take advantage of the work the workers already did. Don't simply sort everything again.
• Do not modify the caller's input list.

Constraints

• 0 <= len(nums) <= 10^6, 1 <= k <= 64, and values fit in a 32-bit signed integer.
• k may be larger than len(nums). Never start a thread for an empty segment.
• Duplicates and negative values are allowed.

Example 1

nums = [12, -4, 7, 7, 0, 30, 5], k = 3
segments: [12, -4, 7] | [7, 0] | [30, 5]
after workers: [-4, 7, 12] | [0, 7] | [5, 30]
result: [-4, 0, 5, 7, 7, 12, 30]

Example 2

nums = [8, 2], k = 6
only 2 workers are used: [8] | [2]
result: [2, 8]

State the time and space complexity of the worker phase and of the combine phase, and explain what makes the result safe to read once the workers are done.