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.