Page 389 - Discrete Mathematics and Its Applications

368 5 / Induction and Recursion

algorithm, and then merging the two lists. The recursive version of the merge sort is given in
Algorithm 9. This algorithm uses the subroutine merge, which is described in Algorithm 10.

ALGORITHM 9 A Recursive Merge Sort.

procedure mergesort(L = a 1 ,...,a n )
if n> 1 then
m := n/2
L 1 := a 1 ,a 2 ,...,a m
L 2 := a m+1 ,a m+2 ,...,a n
L := merge(mergesort(L 1 ), mergesort(L 2 ))
{L is now sorted into elements in nondecreasing order}

An efficient algorithm for merging two ordered lists into a larger ordered list is needed to
implement the merge sort. We will now describe such a procedure.
EXAMPLE 10 Merge the two lists 2, 3, 5, 6 and 1, 4.

Solution: Table 1 illustrates the steps we use. First, compare the smallest elements in the two
lists, 2 and 1, respectively. Because 1 is the smaller, put it at the beginning of the merged list
and remove it from the second list. At this stage, the first list is 2, 3, 5, 6, the second is 4, and
the combined list is 1.
Next, compare 2 and 4, the smallest elements of the two lists. Because 2 is the smaller, add
it to the combined list and remove it from the first list. At this stage the first list is 3, 5, 6, the
second is 4, and the combined list is 1, 2.
Continue by comparing 3 and 4, the smallest elements of their respective lists. Because 3
is the smaller of these two elements, add it to the combined list and remove it from the first list.
At this stage the first list is 5, 6, and the second is 4. The combined list is 1, 2, 3.
Then compare 5 and 4, the smallest elements in the two lists. Because 4 is the smaller of
these two elements, add it to the combined list and remove it from the second list. At this stage
the first list is 5, 6, the second list is empty, and the combined list is 1, 2, 3, 4.
Finally, because the second list is empty, all elements of the first list can be appended to
the end of the combined list in the order they occur in the first list. This produces the ordered
list 1, 2, 3, 4, 5, 6. ▲
We will now consider the general problem of merging two ordered lists L 1 and L 2 into
an ordered list L. We will describe an algorithm for solving this problem. Start with an empty
list L. Compare the smallest elements of the two lists. Put the smaller of these two elements at
the right end of L, and remove it from the list it was in. Next, if one of L 1 and L 2 is empty,
append the other (nonempty) list to L, which completes the merging. If neither L 1 nor L 2 is
empty, repeat this process. Algorithm 10 gives a pseudocode description of this procedure.

TABLE 1 Merging the Two Sorted Lists 2, 3, 5, 6 and 1, 4.
First List Second List Merged List Comparison

2356 14 1 < 2
2356 4 1 2 < 4
356 4 12 3 < 4
56 4 123 4 < 5
56 1234
123456