Design a divide and conquer algorithm for merge sort such that you divide the array into three equal subproblems instead of two.

a) Write the function mergeSort3(int A[], int low, int high) that sorts an array by dividing in into approximately three equal thirds, recursively sorting each third, and then combining all three sorted subarrays into a sorted array.

b) Write a function merge3(int A[], int low, int mid1, int mid2, int high) that combines three sorted subarrays A[low .. mid1], A[mid1...mid2], A[mid2...high] into a sorted array.

c) Analyze the asymptotic running time of your algorithm

Answer rating: 100% (QA)

aPython def mergeSort3A low high if low high mid1 low high low 3 mid2 low 2 h... View the full answer