Practice/xAI/Multi-threaded Array Sort

Multi-threaded Array Sort

CodingMust

Problem Overview

Given a large array of integers, implement a function to sort the array using multiple threads. Your solution should leverage parallelism to improve sorting performance over a single-threaded approach.

The core idea is divide-and-conquer with parallelism:

• Divide the array into chunks (one per thread)
• Sort each chunk independently in parallel
• Merge all sorted chunks into the final result

Important Notes

• Consider the Python GIL (Global Interpreter Lock) which limits true CPU parallelism for pure Python code
• For very large arrays or maximum performance, consider using multiprocessing instead of threading
• Thread overhead can make parallel sorting slower for small arrays
• The merge phase can become a bottleneck if not optimized

Approach 1: Basic Implementation with Sequential Merge

Split the array into k chunks (one per thread), sort each chunk in parallel using the built-in sorted() function, then merge sorted chunks sequentially.

Example

` arr = [38, 27, 43, 3, 9, 82, 10] result = parallel_sort(arr, num_threads=4)

Returns: [3, 9, 10, 27, 38, 43, 82]

`

Requirements

• Handle edge cases: empty arrays, single elements, arrays smaller than thread count
• Each thread sorts its chunk independently
• Merge sorted chunks two at a time
• Return a new sorted array (don't modify input)

Clarification Questions to Ask

• Can we modify the input array in place, or should we return a new array?
• Is the number of threads fixed, or should we dynamically adjust based on array size?
• What's the expected size of the input array? (Helps decide thread overhead trade-offs)
• Should we fall back to sequential sort for small arrays?
• Are there memory constraints? (Merge sort requires O(n) extra space)
• What should happen if num_threads is larger than the array length?

Approach 2: K-Way Merge with Priority Queue

The key optimization over Approach 1 is using a min-heap to merge all k sorted chunks simultaneously. This improves merge complexity from O(n × k) to O(n log k).

Example

`

With 4 threads, array is split into 4 chunks

arr = [5, 2, 9, 1, 7, 6, 3, 8, 4]

Chunks after sorting: [5, 9], [1, 2], [3, 7], [4, 6, 8]

K-way merge using heap combines all at once

result = parallel_sort(arr, num_threads=4)

Returns: [1, 2, 3, 4, 5, 6, 7, 8, 9]

`

Requirements

• Use a min-heap to efficiently select the smallest element from k chunks
• Each heap entry contains (value, array_index, element_index)
• After popping the smallest element, push the next element from the same array
• Continue until all elements are processed