# 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*.

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.

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

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