Multithreaded Integer Sort

Sort an integer array, but the solution must use multiple threads. Single-threaded `sort()` is rejected outright. The expected approach is a parallel merge / parallel quick sort that partitions the input across worker threads and merges results. Requirements Input is a list of integers; return the same list sorted ascending. The implementation must use multiple threads — sorted(arr) or arr.sort() does not pass. Be ready to defend complexity (O(n log n) work, O(n / p + n) time on p cores) and to discuss when the parallel version actually beats single-threaded sort given GIL and merge overhead. Common follow-ups: cap thread count to a fixed pool, switch from threads to processes, and reason about cache behavior on the merge step. Canonical OA signature: def parallel_sort(arr: list[int], num_threads: int) -> list[int]: ... # Split into min(num_threads, len(arr)) chunks, sort each chunk in its own thread, then merge. # Return a new ascending-sorted list; fall back to sorted(arr) below a size threshold. Notes The accepted shape is parallel merge sort: partition the array into p chunks, sort each chunk in its own thread, then merge pairwise (sequentially is fine; the round rarely demands a parallel merge step). Merge strategy matters as p grows: pairwise sequential merge is O(n·p), while a k-way min-heap merge (push one head per chunk, pop-and-refill from the same chunk) is O(n log p). Reach for the heap merge when the thread count is large. In Python, the GIL means CPU-bound parallel sort with threads is rarely faster than a single sorted() — interviewers know this and accept the answer as a correctness exercise; if asked for actual speedup, pivot to multiprocessing or NumPy. Avoid spawning a thread per element; the hidden bar is that you cap concurrency at min(p, log n) levels of recursion. Concrete fall-back thresholds from the canonical OA: sort directly with sorted() below ~10_000 elements, and size chunks so each holds at least ~1_000 elements (chunk_count = max(1, min(num_threads, n // 1000))) — below that, thread-management overhead outweighs the parallel win. This problem is publicly mirrored on the hack2hire "xai" listing as multithread sorting. Preparation Write a parallel merge-sort skeleton from scratch in 10 minutes: split, ThreadPoolExecutor.map, recursive merge. Be able to articulate why the GIL ruins CPU-bound speedup in CPython and how multiprocessing.Pool would change the picture. Practice the merge step in place to avoid O(n log n) extra memory — interviewers ask about memory pressure when n is large. Know the standard concurrent.futures defaults: ThreadPoolExecutor defaults to min(32, cpu_count + 4) workers (tuned for I/O-bound work), while ProcessPoolExecutor defaults to cpu_count (right for CPU-bound work). For a CPU-bound parallel sort in CPython, switch to ProcessPoolExecutor so the GIL does not serialize the chunk sorts; objects must be picklable, so a list[int] works but lambdas as the sort key do not. Use executor.map(sorted, chunks) for the per-chunk sort step; reserve submit + as_completed only when you need to start merging early.