Let S1 and S2 be two sets where |S1| = m, |S2| - r, for m, r ∈ Z+, and the elements in each of S1, S2 are in ascending order. It can be shown that the elements in S1 and S2 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| = 2n. Prove that the number of comparisons needed to place the elements of S in ascending order is bounded above by n ∙ 2n.