Multi-Core Merge Sort Optimization

Problem Given a standard single-threaded merge sort, modify it to exploit a k-core machine, and compare the resulting time complexity across five settings: standard merge sort on 1 core, standard merge sort on k cores, the modified (parallel) merge sort on 1 core, the modified version on k cores, and the modified version running k threads.

Input / Output

• Input: an array of n comparable elements and a core/thread budget k.
• Output: the sorted array, plus a reasoned complexity comparison across the five settings.

Constraints

• Assume k <= n.
• Thread creation and synchronisation overhead are reasoned about analytically, not benchmarked.
• Memory is the usual O(n) merge scratch buffer; the merge step is the sequential bottleneck unless it too is parallelised.

Example

• n = 10^6 elements with k = 8 cores: the parallel version farms the eight independent subarray sorts across cores, but the final merge of two 500k-element halves still runs on a single thread — the concrete case that exposes the sequential-merge bottleneck and explains why the speedup is not 8x.