Sort a Large Array Using Multiple Threads
Company: xAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# 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.
Quick Answer: This question evaluates understanding of concurrent programming, parallel algorithm design, sorting algorithms, and merging techniques under multi-threaded execution, focusing on thread-safety, deterministic correctness despite scheduling variability, and performance trade-offs.
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 (`threading.Thread` in Python, `std::thread` in C++, `Thread`/`ExecutorService` in Java). Each thread may use any standard comparison sort on its own chunk. The main thread must wait for all workers to finish before merging.
3. **Merge** the `k` sorted chunks into one fully sorted array. The merge must not re-sort the concatenated data — it must exploit that the chunks are already sorted. The intended approach is a **k-way merge using a min-heap (priority queue)**, merging `n` total elements across `k` sorted runs in `O(n log k)` time.
Each worker should own exactly its chunk (no unsynchronized shared writes) so the result is deterministic regardless of thread scheduling. Return the fully sorted array.
### Example
```
nums = [5, 2, 9, 1, 7, 3], k = 2
Chunks: [5, 2, 9] [1, 7, 3]
After parallel sort: [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.
- k may be greater than the array length (clamp to at most n non-empty chunks).
- The array may be empty.
- Duplicates are allowed and must all appear in the output.
Examples
Input: ([5, 2, 9, 1, 7, 3], 2)
Expected Output: [1, 2, 3, 5, 7, 9]
Explanation: Two chunks [5,2,9] and [1,7,3] sort to [2,5,9] and [1,3,7]; the k-way merge interleaves them into the fully sorted array.
Input: ([], 3)
Expected Output: []
Explanation: Empty array: no chunks to sort or merge, so the result is empty regardless of k.
Hints
- Compute chunk boundaries with base = n // k and rem = n % k so the first `rem` chunks are one element larger; this handles k > n and empty input cleanly.
- Give each thread its OWN chunk list (a copy of the slice) so there is no shared mutable state — the merge stays deterministic no matter the scheduling order.
- For the merge, push the head (value, chunk_index, element_index) of every non-empty chunk into a min-heap; pop the smallest, append it, then push the next element from that same chunk. This is O(n log k), not O(n log n).