This is the question about Merge Sort, Please help nem solve it!

Given an array A, the merge sort algorithm always divides A into two half- arrays of approximately the same size, recursively sort the half arrays and finally merge them. The pseudo-code for this algorithm is presented below.

 mergesort(A, left, right) { if( left < right ) { 

 center = (left + right) / 2; mergesort(A, left, center); mergesort(A, center + 1, right); merge(A, left, center + 1, right); 

} }

Now we propose a new algorithm, mergesort3(A, left, right), which uses almost the same strategy as in mergesort, except that mergesort3 divides A into 3 sub-arrays of approxi- mately the same size.

1)Write down the pesudo-code for mergesort3. Note: The mergesort function calls another function merge(A, i1, i2, i3) which merges two sorted arrays, A[i1..i2 1] and A[i2..i3] into one. You may continue to call this function in mergesort3.

2)What is the running-time complexity for mergesort3? Prove your answer.