Question
Implement an ascending integer sort that divides sufficiently large inputs into chunks, sorts chunks concurrently, and merges the sorted runs. ```python def parallel_sort(values: list[int], num_workers: int) -> list[int]: ... ``` Return a new list and do not mutate the input. For fewer than `1000` values or a single worker, a direct sort is acceptable. On the large-input path, actually partition the input and dispatch chunk sorts; do not sort the entire list in one call. Cap the worker count to useful work and merge all runs correctly, including duplicates and negative values. The worker count must be a positive integer (not a boolean); reject invalid counts with `ValueError` before dispatch. Use native worker execution for the concurrent path. The supplied `run_case` is fixture glue, not candidate work. Public result checks establish sorting and input ownership; a correct sequential sort can pass those result checks, so concurrent chunk dispatch requires a separate execution witness. ## Staged follow-ups 1. Compare pairwise merging with a `k`-way heap merge. 2. Explain why threads may not accelerate CPU-bound Python code and when processes help. 3. Bound memory usage or merge in place. 4. Begin producing results before every chunk has completed.