Multi-Core Merge Sort Optimization

Problem: Given standard merge sort running on a single core, how would you modify it to take advantage of a k-core system for optimal time complexity? Compare time complexities across: standard merge sort on 1 core, standard merge sort on k cores, modified (parallel) merge sort on 1 core, modified merge sort on k cores, and modified merge sort using k threads.

Constraints: Assume k <= n (array size) and that thread creation/synchronization overhead is analyzed conceptually, not benchmarked.

Example: For n elements, standard single-core merge sort is O(n log n). With k cores/threads, the recursive divide step can farm out independent subarray sorts to separate threads.

Approach: Parallelize the recursive 'divide' phase: while the subarray size is large relative to the number of available threads, spawn a new thread/task for one half's sort while the current thread handles the other half, then merge sequentially (or also parallelize the merge for very large arrays using a parallel merge algorithm). With k independent cores and enough parallel depth, achievable time complexity approaches O((n log n)/k) for the sorting phase, though the sequential merge step and thread overhead mean real speedup is sub-linear; with only k threads instead of k dedicated cores, context-switching overhead further limits gains.