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