How can I prove that this is the upper bound?

[SpatialVacancy1]

Combinatorics...evil problem!

Hi all,

I am working on my combinatorics homework. I have completed all of the problems but one. Here it goes:

------------------------------------------
Let S_1 and S_2 be two sets where |S_1| = m and |S_2| = r, for m,r in Z+ (positive integers), and the elements in each of S_1, S_2 are in ascending order. It can be shown that the elements in S_1 and S_2 can be merged into ascending order by making no more than m + r - 1 comparisons. Use this result to establish the following:

For n >= 0, Let S be a set with |S| = 2^n. Prove that the number of comparisons needed to place the elements of S in ascending order is bounded above by n * 2^n.
------------------------------------------

Please help! Due by 12:00 PM EST tomorrow the 3rd!

 

[vsage]

I was able to produce the right result by breaking S into one element sets then combining pairs of them to create half as many sets of two elements and assuming it took the upper bound of m+r-1 comparisons to create each set. I then combined pairs of two element sets to create half as many sets of 4 elements, and so on until I had one set of 2^n elements (S), and summed the upper bounds of all of comparisons required to make each intermediate set and finally S.