Give a complete justification of Theorem 4.1, which says: "The merge-sort tree associated with an execution of merge-sort on a sequence of size n has height ceil(logn)."

------------------
Juztyn
Taking credit for: Canyon Stream, Higher Ground, The Space Between, Death's Dome (mlp3), bits of JKRPG, and the entire Showcase forum, damnit!... Visit SWGalaxies.net for the latest Star Wars: Galaxies information!

You mean:

Merge Sort Tree:
- Take a binary tree T
- Each node of T represents a recursive call of the
merge sort algorithm.

?

I would look at how Merge Sort splits the array/sequence

------------------
"Music is the universal language and the
dialect we speak in is Hip Hop!" - King Solomon

A merge sort tree is something like this:



And then sorts on the way back up. It's recursive.

------------------
J-uztyn
Taking credit for: Canyon Stream, Higher Ground, The Space Between, Death's Dome (mlp3), bits of JKRPG, and the entire Showcase forum, damnit!... Visit SWGalaxies.net for the latest Star Wars: Galaxies information!

[This message has been edited by Juztyn (edited June 30, 2004).]

2?

------------------
<S51> Give a man a sandwich and you'll feed him for an hour, teach him to make a sandwich and he'll get pissed, hit you and tell you to make him another sandwich.

------------------
"Music is the universal language and the
dialect we speak in is Hip Hop!" - King Solomon

I just threw the proof for a perfect binary tree's height at it. Should be enough. Thx guys.

------------------
Juztyn
Taking credit for: Canyon Stream, Higher Ground, The Space Between, Death's Dome (mlp3), bits of JKRPG, and the entire Showcase forum, damnit!... Visit SWGalaxies.net for the latest Star Wars: Galaxies information!

it should be, it's the same proof.

log with base 2 because each tree has 2 subtrees.

I have a different strategy: I'll wait until you do all the work, and then I'll copy it, modify it just a little bit to avoid lawsuits, slap some eye candy on it to hide the flaws created during the modification process, and sell it. I can be just like Microsoft.



------------------
The University of North Carolina has finally found a network server that, although missing for four years, hasn't missed a packet in all that time. Try as they might, university administrators couldn't find the server. Working with Novell Inc., IT workers tracked it down by meticulously following cable until they literally ran into a wall. The server had been mistakenly sealed behind drywall by maintenance workers.

oh im sorry, the correct answer was pie

------------------
*landfish 'splodes*
7 of 14

Oooooh I like pie... specially with ice cream.

------------------
They call him El Diablo... *whip crack*

Pie's just not the same without cheese.