So the question is, how do we efficiently combine these two sorted subarrays to form the sorted version of the original array? The answer: I wish I had an algorithm "merge" that would do that for me!Algorithm:sort(A,i,j) if i == j return m = (i + j)/2 ← divide r1 = sort(A,i,m) ← conquer r2 = sort(A,m+1,j) ????? ← combine

This version of merge should be fairly easy to understand, so I won't worry about proving correctness. What about its running time? Best and worst case running times are both $\Theta(n)$, which we derived in class (and is done in the unit notes).Algorithm:merge(A,i,m,j) Inputs : array A, and indices i ≤ m ≤ j such that A[i..m] and A[(m+1)..j] are idividually in sorted order Outputs: array A is modified so that A[i..j] contains its original elements in sorted order A1 = new array copy of A[i..m] A2 = new array copy of A[(m+1)..j] k = i, i1 = 0, j1 = m - i, i2 = 0, j2 = j - (m+1) while i1 ≤ j1 and i2 ≤ j2 do ← keep adding the smaller of the initial elements of A1 & A2 if A2[i2] < A2[i1] A[k] = A2[i2], i2 = i2 + 1, k = k + 1 else A[k] = A1[i1], i1 = i1 + 1, k = k + 1 while i1 ≤ j1 do ← add any remaining elements of A1 A[k] = A1[i1], i1 = i1 + 1, k = k + 1 while i2 ≤ j2 do ← add any remaining elements of A2 A[k] = A2[i1], i1 = i1 + 1, k = k + 1 free A1 and A2

In class we made a start on analyzing mergesort. If we use $T_w(n)$ to denote mergesort's worst-case running time as a function of the input array size, we end up with the following: that for some constant $c$, for all $n \gt 0$ \[ T_w(n) \leq T_w\left( \lceil n/2 \rceil \right) + T_w\left( \lfloor n/2 \rfloor \right) + c n \] where the floor and ceiling are required because with an odd-sized range, we cannot divide evenly in half. This is a bit difficult to analyze, so let's get rid of the floor and ceiling business, by noting that since $\lceil n/2 \rceil \leq (n+1)/2$ and $\lfloor n/2 \rfloor \leq (n+1)/2$, and we are assuming that $T_w(n)$ is a non-decreasing function (in other words that it doesn't get faster as the input gets larger), we can weaken our upper bound to \[ T_w(n) \leq 2\ T_w\left(\frac{n+1}{2}\right) + c n. \] Finally, we note that any function $f$ that satisfies that same recurrence with equality is an upper bound on $T_w$. So if we solve \[ f(n) = 2\ f\left(\frac{n+1}{2}\right) + c n \] for $f(n)$, then we will know $T_w(n) \in O(f(n))$. Great! Now that we have a recurrence relation, let's see if Mathematica can solve it for us:Algorithm:msort(A,i,j) if i == j return m = (i + j)/2 ← divide r1 = msort(A,i,m) ← conquer r2 = msort(A,m+1,j) merge(A,i,m,j) ← combine

Hopefully you can pick out the dominant term in this: it's $c n \lg (n-1)$ which is $O(n \lg n)$. And so we get $T_w(n) \in O(n \lg n)$. You should be excited! This is much better than the $\Theta(n)$ worst-case bound we have for insertionSort, and selectionSort (and indeed gnomeSort).

For a lower bound on $T_b(n)$, we do the same basic thing.
Since merge is $\Theta(n)$ for both best and worst case, for
some constant $d$ the merge will take at least $d n$, and
since $(n-1)/2$ is less than or equal to both $\lfloor n/2 \rfloor$
and $\lceil n/2 \rceil$, we get
$T_b(n) \geq 2 T_b\left((n+1)/2\right) + c n$. A function
$g$ that satisfies this with equality is a lower bound on
$T_b(n)$, so we solve
$g(n) = 2 g((n-1)/2) + d n$ with Mathematica

and get that $g(n) \in \Omega(n \lg n)$. That means
$T_b(n) \in \Omega(n \lg n)$.

**Finally ...**
Since the worst case is $O(n \lg n)$ and the best case is
$\Omega(n \lg n)$, we get that $T_w(n)$ and $T_b(n)$ are both
$\Theta(n \lg n)$.