MergeSort demo with n not a power of 2

This page demonstrates MergeSort on 21 elements. If you haven't already, then you should visit the main MergeSort demo page first.

Contents:


What if n isn't a power of 2?

Let's look at the recurrence relation for T(n) again:
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) + 21
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
Again, we bounce back up:
T(1) = 0
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
So MergeSort needs no more than 94 comparisons to sort an array of 21 elements.

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.

(Source code for the applet.)
To view this applet, you need to use a web browser that understands Java applets that use the Java 1.0 API. As of May 29, 1996, Netscape 2.02 and IBM WebExplorer (beta) are the only ones that do.

<-- These param's are disabled. As of March 28, 1996, Netscape sometimes passes a null value in place of the actual value. I don't know why. I have hardcoded these constanst in the source code instead. Blech. -->


Feedback

Please help me to make this a better web page and applet. Send me email with whatever suggestions you have.

Thanks,
David


Copyright 1996, David Neto.
Professor Allan Borodin aided in the conceptual design of the applet.
Back to David Neto's main MergeSort demo page
Back to David Neto's teaching page
Back to David Neto's Java page
Back to David Neto's home page