Contents:
T(n) = 0, if n<2.
T(n) = T(n/2) + T(n/2) + n, if n>1.
Notice that the second equation only makes sense when n/2 is a natural number, and therefore only when n is even. If n/2 is itself larger than 1, the same reasoning applies, and our equation makes sense only when n/2 is itself even. Repeating this, we see that we have defined T(n) only for those n which are powers of two.
The problem arises when n is odd, i.e. when the array cannot be split evenly in half. In that case, instead of looking at values of T for n/2, we should use the actual lengths of the two parts. In general, left ``half'' will have floor(n/2) elements and the right ``half'' will have ceil(n/2). (If you haven't seen these functions already, floor(x) returns the greatest integer not more than x, and ceil(x) returns the least integer not less than x.)
So the equations can be rewritten as follows:
T(n) = 0, if n<2.
T(n) = T(floor(n/2)) + T(ceil(n/2)) + n, if n>1.
Computing T(21)
The n=21 case is an instructive example.
As before, we expand the recursion until we hit bottom. This time, however,
we get to reuse fewer results.
T(21) = T(10) + T(11) + 21Again, we bounce back up:
T(11) = T(5) + T(6) + 11
T(10) = T(5) + T(5) + 10
T(6) = T(3) + T(3) + 6
T(5) = T(2) + T(3) + 5
T(3) = T(1) + T(2) + 3
T(2) = T(1) + T(1) + 2
T(1) = 0
T(1) = 0So MergeSort needs no more than 94 comparisons to sort an array of 21 elements.
T(2) = T(1) + T(1) + 2 = 0 + 0 + 2 = 2
T(3) = T(1) + T(2) + 3 = 0 + 2 + 3 = 5
T(5) = T(2) + T(3) + 5 = 2 + 5 + 5 = 12
T(6) = T(3) + T(3) + 6 = 5 + 5 + 6 = 16
T(10) = T(5) + T(5) + 10 = 12 + 12 + 10 = 34
T(11) = T(5) + T(6) + 11 = 12 + 16 + 11 = 39
T(21) = T(10) + T(11) + 21 = 34 + 39 + 21 = 94
MergeSort in action on 21 elements
The following applet sorts 21-element arrays. It works in the same
way as the applet on
the main mergesort demo page.
Thanks,
David