Hand-Write a Parallel Sort Using Multiple Worker Threads or Processes

Implement a parallel sort by hand. Write a function `parallel_sort(values, num_workers)` that returns the elements of `values` in ascending order, exactly what a sequential sort would return, while splitting the work across up to `num_workers` concurrent workers (threads or processes). ```python def parallel_sort(values: list[int], num_workers: int) -> list[int]: ... ``` The parallel structure must be your own code: how the input is divided, how workers are started, coordinated and joined, and how their partial results are combined into one sorted list. A single call to a library routine that already sorts in parallel does not count. ```hint Split, then combine Decide what each worker receives and what it hands back, then work out what it costs to turn those partial results into one sorted list. ``` ```hint Find the serial part Identify the phase of your design that still runs on a single worker, and estimate how much it limits the speedup as `num_workers` grows. ``` ### Constraints and Clarifications - The result must equal `sorted(values)` for every input, including an empty list, many duplicates, and `num_workers` larger than `len(values)`. - `num_workers >= 1`. - If any worker fails, the call must raise an error instead of returning a partial result. ### Clarifying Questions - Which language and runtime? In CPython, do threads give real parallelism for CPU-bound sorting, or should the solution use processes? - Roughly how large are the inputs, and how many cores are available? Is falling back to a sequential sort below some input size acceptable? - May each worker use the language's built-in sequential sort on its piece, or must every step be hand-written? - Must the sort be in place, or may it return a new list? Is stability required when records are sorted by a key? - Are the values plain integers, or large objects that are expensive to move between workers? ### What a Strong Answer Covers - A decomposition with an argument that the combined output equals a sequential sort - The worker lifecycle: start, join, a bounded number of workers, and error propagation - A choice between threads and processes that fits the runtime, with the copying cost it implies - Work and span analysis that names the sequential bottleneck and how to shrink it - Handling of small inputs, skewed data and heavy duplication - A test plan that compares the result with a sequential sort on adversarial inputs ### Follow-up Questions - Your final combine step runs on one worker. How would you parallelize it? - How would you choose partition boundaries so that every worker gets a similar amount of data when values are skewed or heavily duplicated? - The data no longer fits in the memory of one machine. What changes in the design? - How would you write this in Go with goroutines, or in Java with a fixed thread pool, and what would you do differently from Python?