[Solved]: Showing that tournament sort requrires O(n log n) comparisons

Problem Detail: 

I wish I could think of a better way to word my question. Maybe some one here could offer s suggestion for that, as well.

On to my question. Before I do, this is a class question that has been asked, answer, and considered to be over; however, I'm struggle accepting the answer. For this reason, I'm here hoping someone can word it in a way that I understand it.

The problem is as follows:

Show that if n is a power of 2, tournament sort requires O(n lg n) comparisons. 

I refer to a rooted tree graph of six levels (0-5) with the vertices doubling at each level: i.e 1, 2, 4, 8, 16, 32. I see a pattern very similar to binary. I'm not implying the problem is binary related, but it is powers of 2 and I'm very comfortable with binary.

Using that 2^5 = 32, n=32; therefore, n is a power of 2. No argument here. Now I read the problem to say that 32log32 (nlogn) will result in the number of comparisons. The aide answering my question said, "the calculated results of the nlogn were immaterial. I just needed to know there were 5 levels down, and therefore 5 levels up." Additionally, he kept referring to 5log5 which I still don't see a result that makes any sense to me.

As I study the question, I read it to say that the nlogn should provide me with a number of comparisons, based on n. I cannot make that happen with a known values.

Can someone please help me to follow this better?

Asked By : Lee

Answered By : FrankW

Initially you place the elements you want to sort in the leaves of the tournament tree. Then you fill all the internal nodes with the bigger of the two elements in their respective children. This takes $n-1$ comparisons.

After that, you have the largest element in the root. So you can remove it and place it in the output. Now all the comparisons where this element was involved have to be redone. This is one comparison per level of the tree, making $(\log n) -1$ comparisons (-1, since on the lowest level, there is only one candidate element left, so you don't need to compare.)

Now the second largest element is at the top and you can repeat the procedure. And so on. In the end you will have made up to $\log n$, i.e. $O(\log n)$ comparisons for each of the $n$ elements.

Summing up, we have $n-1 + n\cdot O(\log n)$ comparisons. By the rules of $O$-notation, that is in $O(n\log n)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29900