These notes and closely review Unit 2 Section 2.



Review: Applying Divide & Conquer to sorting

Next we decided to try applying Divide and Conquer to the problem of sorting. This is where we got to:
Algorithm: sort(A,i,j)

if i == j

m = (i + j)/2          ← divide

r1 = sort(A,i,m)       ← conquer
r2 = sort(A,m+1,j)

?????                  ← combine
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!


Ask and you shall receive, here is an algorithm for merging two consecutive sorted subranges.
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
    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
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).

Mergesort completed ... and analyzed

So here's mergesort, a divide and conquer sorting algorithm.
Algorithm: msort(A,i,j)

if i == j

m = (i + j)/2           ← divide

r1 = msort(A,i,m)       ← conquer
r2 = msort(A,m+1,j)

merge(A,i,m,j)          ← combine
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:

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)$.