Page 390 - Discrete Mathematics and Its Applications

5.4 Recursive Algorithms 369

We will need estimates for the number of comparisons used to merge two ordered lists in the
analysis of the merge sort. We can easily obtain such an estimate for Algorithm 10. Each time
a comparison of an element from L 1 and an element from L 2 is made, an additional element
is added to the merged list L. However, when either L 1 or L 2 is empty, no more comparisons
are needed. Hence, Algorithm 10 is least efficient when m + n − 2 comparisons are carried out,
where m and n are the number of elements in L 1 and L 2 , respectively, leaving one element in
each of L 1 and L 2 . The next comparison will be the last one needed, because it will make one
of these lists empty. Hence, Algorithm 10 uses no more than m + n − 1 comparisons. Lemma 1
summarizes this estimate.

ALGORITHM 10 Merging Two Lists.

procedure merge(L 1 ,L 2 : sorted lists)
L := empty list
while L 1 and L 2 are both nonempty
remove smaller of first elements of L 1 and L 2 from its list; put it at the right end of L
if this removal makes one list empty then remove all elements from the other list and
append them to L
return L{L is the merged list with elements in increasing order}

LEMMA 1 Two sorted lists with m elements and n elements can be merged into a sorted list using no
more than m + n − 1 comparisons.

Sometimes two sorted lists of length m and n can be merged using far fewer than m + n − 1
comparisons. For instance, when m = 1, a binary search procedure can be applied to put the
one element in the first list into the second list. This requires only log n comparisons, which
is much smaller than m + n − 1 = n, for m = 1. On the other hand, for some values of m
and n, Lemma 1 gives the best possible bound. That is, there are lists with m and n elements
that cannot be merged using fewer than m + n − 1 comparisons. (See Exercise 47.)
We can now analyze the complexity of the merge sort. Instead of studying the general
m
problem, we will assume that n, the number of elements in the list, is a power of 2, say 2 . This
will make the analysis less complicated, but when this is not the case, various modifications can
be applied that will yield the same estimate.
At the first stage of the splitting procedure, the list is split into two sublists, of 2 m−1 elements
each, at level 1 of the tree generated by the splitting. This process continues, splitting the two
sublists with 2 m−1 elements into four sublists of 2 m−2 elements each at level 2, and so on. In
general, there are 2 k−1 lists at level k − 1, each with 2 m−k+1 elements. These lists at level k − 1
k
are split into 2 lists at level k, each with 2 m−k elements. At the end of this process, we have 2 m
lists each with one element at level m.
m
We start merging by combining pairs of the 2 lists of one element into 2 m−1 lists, at level
m − 1, each with two elements. To do this, 2 m−1 pairs of lists with one element each are merged.
The merger of each pair requires exactly one comparison.
k
The procedure continues, so that at level k(k = m, m − 1,m − 2,..., 3, 2, 1), 2 lists
each with 2 m−k elements are merged into 2 k−1 lists, each with 2 m−k+1 elements, at level k − 1.
To do this a total of 2 k−1 mergers of two lists, each with 2 m−k elements, are needed. But,