However it involves less data movement. We can prove that the lower bound on sorting is actually . The approach for reaching this lower bound is to use divide and conquer. Sorting is easier on short lists than long list. For example in previous algorithms we have behavior.
Key question is how to partition the two lists.
Will look at two approaches. At each point simply divide the list into two and sort each list. We can have no more comparisons than elements being merged. Hence if we look at Figure 7.10 we see a total of n elements at each level and levels for a total of . Thus merge sort is in number of comparisons.