# MergeSort demo with comparison bounds

This page demonstrates MergeSort. At the same time, it shows the number of comparisons actually used, and a worst case upper bound on this number.

Contents:

## Description of MergeSort

MergeSort is a recursive sorting procedure that uses O(n log n) comparisons in the worst case. To sort an array of n elements, we perform the following three steps in sequence:
• If n<2 then the array is already sorted. Stop now.
• Otherwise, n>1, and we perform the following three steps in sequence:
1. Sort the left half of the the array.
2. Sort the right half of the the array.
3. Merge the now-sorted left and right halves.

## Time bounds

To get an idea of how long MergeSort takes, we count the number of comparisons it makes in the worst case. Call this function M(n). We parameterize it by the size of the array, n, because MergeSort takes longer on longer inputs.

It is difficult to describe M(n) exactly, so instead we describe a simpler function T(n) which bounds M(n) from above, i.e. M(n) <= T(n).

## An expression for T(n)

Because MergeSort has two cases, the description of T also has two cases. The base case is just
T(n) = 0, if n<2.

The induction case says that the number of comparisons used to sort n items is at most the sum of the worst-case number of comparisons for each of the three steps of the induction case of MergeSort. That is,

T(n) = T(n/2) + T(n/2) + n, if n>1.
Let's look at this expression one term at a time.

The first term accounts for the number of comparisons used to sort the left half of the array. The left half of the array has half as many elements as the whole array, so T(n/2) is enough to account for all these comparisons.

The second term is a bound on the number of comparisons used to sort the right half of the array. Like the left half, T(n/2) is enough here.

The last term, n is an upper bound on the number of comparisons used to merge two sorted arrays. (Actually, n-1 is a tighter bound, but let's keep things simple.)

## Recursive definitions and recurrence relations

Now, something interesting is going on here. The inductive case defines T in terms of itself! This is called a recursive definition. The function T has a recursive definition because the description of MergeSort itself is recursive.

When a numerical expression is defined recursively, we call its set of defining equations a recurrence relation.

Recursive definitions (and recurrence relations) only make sense if we ``hit bottom'' at some point. That is, unless the recursion terminates, we can't assign meaning to T(n). That's why we needed the base case.

## T(n) for particular n

Suppose we want to sort 16 elements with MergeSort. What does the recurrence tell us? Well, this job will require no more than T(16) comparisons.

How do we compute T(16)? One way is to unfold the recurrence all the way until we hit bottom.

T(16) = 2T(8) + 16
T(8) = 2T(4) + 8
T(4) = 2T(2) + 4
T(2) = 2T(1) + 2
T(1) = 0
Now that we've hit bottom, we can ``bounce back up'' by substituting up this table.
T(1) = 0
T(2) = 2T(1) + 2 = 0 + 2
T(4) = 2T(2) + 4 = 4 + 4 = 8
T(8) = 2T(4) + 8 = 16 + 8 = 24
T(16) = 2T(8) + 16 = 48 + 16 = 64

So MergeSort requires at most 64 comparisons to sort 16 elements. Lets see if this is true.

## MergeSort in action

The following applet is a working version of MergeSort. It sorts an array of sixteen bars. Click the Go button and watch it sort the blue bars into green bars. I will explain more below.

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 constants in the source code instead. Blech. -->

Ok. I hope you've seen it sort at least once. Now I'll explain the applet in a bit more detail.

### What's happening, and what are those colours?

In the beginning, there is an array of bars that are unsorted. Unsorted bars are coloured blue (a dark grey on a black and white screen).

To sort the left half of the array, the program calls itself recursively, passing the left half of the bars down to a new activation of MergeSort. This happens repeatedly until we have an array of only one element. As noted earlier, one-element arrays are already sorted. Bars in sorted arrays are coloured green (or light grey on a black and white screen).

When the left half of an array is sorted, we sort the right half.

Once the two halves of an array have been sorted by recursive calls, MergeSort merges the two sorted halves into a sorted whole. This is done by examining and comparing the smallest remaining bar in each of the sorted halves. The two bars being compared are coloured red (or medium grey). The smaller of these two bars turns green and is moved up and tacked onto the right end of the parent array.

When one of the two subarrays becomes empty, the remaining bars in the other subarray are copied in order into the parent array. No comparisons need to be made.

That describes the workings of MergeSort. I suggest you go back, click on the ``Load input'' button, then click on the ``Go'' button, and adjust the speed slider so that you can see the comparisons being made. Then come back.

### What are those numbers?

But what about those numbers over the bars? Each array of bars (except for those with only one bar) has an inequality associated with it. The right hand side of the inequality is the upper bound on the number of comparisons required to sort an array of that size. That is, the right hand side is T(n), where n is the number of bars in that array. The left hand side is the actual number of comparisons made so far. This latter figure gets updated as the sorting proceeds.

I have used strict inequality because we have actually overestimated the number of comparisons required for merging by 1 at each level. (To tell you the truth, it's really because I couldn't find a nice-looking less-than-or-equal-to sign that would fit in that space!)

### Trying other inputs

You can specify various canned inputs, i.e. inputs that I've programmed for you, by bringing up a pop-up menu where the word ``Strange'' originally appeared. Note that once you have specified an input, you have to click on ``Load input'' in order for it to be loaded into the array for sorting. Try the various options.

If you are adventurous, you can type in your own values for the heights of the bars by first clicking on the text box next to the input choice menu, and then typing. Actually, you can specify any set of numbers you like, but only the first 16 will be looked at. Even then, the program doesn't use the absolute values as bar heights, but only their relative ordering. If you type in fewer than 16 numbers, then the last number is repeated. For example, to see what MergeSort does when when all the inputs are the same, type in just a single 1 in the text box, then load the input, and click on ``Go''.

If you are adventurous but lazy, then you can just click on the button labelled ``Shuffle now''. This randomly rearranges the numbers in the text box. For interesting results, select the ``Ascending'' input and then shuffle it a few times.

## Further explorations

To better understand all this, try the following exercises: (Note to 238 students: these are not required for your course. I just made these up.)
• What if n isn't a power of 2? Take a look at the n=21 case.
• Tightening the estimation:
• Write down a recurrence relation for T'(n) which uses the tighter estimate of n-1 comparisons for merging two lists into one list of length n.
• Compute the value of T'(16).
• Can you find a 16-element input that forces MergeSort to use T'(16) comparisons?
• Can you describe a worst-case input for MergeSort for general n?
• Can you find a closed form solution for T(n)?
• Can you find a closed form solution for T(n) to within multiplicative and additive constants, i.e. find a closed form expression f(n) so that T(n) is O(f(n))? Hint: the answer to that is on this web page, but its derivation is not.
• What, besides comparisons, takes time when actually sorting arrays?
• What resources, besides time, does the above implementation of MergeSort use? How much? Can you make MergeSort more efficient in that respect?

## Feedback

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

Thanks,
David