Merge Sort on Large Arrays | Dataford Interview Questions

How does merge sort work and what is its time complexity? If you had an 8-core CPU, how would you modify merge sort for a huge array and what would the time complexity be?

Asked in the Round 1 stage. Implement a function that returns a sorted copy of an integer array using the requested number of worker processes. Split the array into chunks, sort chunks independently, then merge them.

Input and Output

nums is a list of integers and cores is a positive integer. Return nums sorted in ascending order without modifying the input.

Constraints

0 <= len(nums) <= 10^5
1 <= cores <= 8
Values fit in a signed 32-bit integer
Return a sorted copy and do not modify nums

Function Signature

def parallel_merge_sort(nums, cores):

Your question is Merge Sort on Large Arrays. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem