**Problem : **
In the course of a merge sort on a 64 element list, how many times must
the list be split?

6 times, or

*log*2(64).

**Problem : **
Consider the following pairs of lists:

- A. (3, 5, 7, 9) and (2, 4, 6, 8)
- B. (1, 2, 3, 4) and (5, 6, 7, 8)

Which pair is more efficiently merged?

Pair B can be merged more efficiently because after four comparisons
the first list is empty. Since we know that the second list is already
in order, we simply insert the elements one by one into the final list
without making any more comparions.

**Problem : **
Below is an 8 element list that has been broken down into 8 one element
lists. Show the merging of the lists to form and ordered list.
(6), (3), (8), (2), (9), (1), (5), (7)

(6) and (3) merge to (3, 6)
(8) and (2) merge to (2, 8)
(9) and (1) merge to (1, 9)
(5) and (7) merge to (5, 7)
(3, 6) and (2, 8) merge to (2, 3, 6, 8)
(1, 9) and (5, 7) merge to (1, 5, 7, 9)
(2, 3, 6, 8) and (1, 5, 7, 9) merge to (1, 2, 3, 5, 6, 7, 8, 9)

**Problem : **
The list above required 7 merges to be sorted. In general, how many merges
will be performed in an n element list (for the sake of simplicity, assume
that n is a power of 2)?

*n*/2 + *n*/4 + *n*/8 + ... + 2 + 1 = *n* - 1