MySort(A[1 ... n):
1. if n > 1:
2. MySort(A[1 ... n/2])
3. MySort(A[n/2+1 ... n])
4. Merge(A[1 ... n])
Merge(A[1 ... m]):
5. if m = 2:
6. swap A[1] and A[2] // this is the only comparison
7. else:
// first swap the 2nd and the 3rd quarter
8. for i = 1 to m/4:
9. swap A[m/2 + i] and A[m/4 + i]
10. Merge(A[1 ... m/2]) // recurse on left half
11. Merge(A[m/2+1 ... m]) // recurse on right half
12. Merge(A[m/4+1 ... 3m/4]) // recurse on middle half
(a [2 points]) Prove that MySort() does not correctly sort if we removed the for-loop from Merge.
(b [2 points]) Prove that MySort() does not correctly sort if we swapped lines 11 and 12.
(c [5 points]) Use induction to prove that Merge() correctly creates a sorted array from two sorted array put one after another. That is, if A[1 ... n/2] is sorted, and A[n/2+1 ... n] is sorted, then after a call to Merge(A[1 .... n]), A will be sorted. Hint: Take an array consisting of n/4 1's, n/4 2's, n/4 3's and n/4 4's (in an arbitrary order) and run MySort() on this array. Hint: Read JE-1.4 for a proof by induction of MergeSort().
(d [3 points]) What is the running time of Merge()? Explain with the help of a recurrence relation.
(e [3 points]) What is the running time of MySort()? Explain with the help of a recurrence relation.