Page 388 - Discrete Mathematics and Its Applications

5.4 Recursive Algorithms 367

8 2 4 6 9 7 10 1 5 3

8 2 4 6 9 7 10 1 5 3

8 2 4 6 9 7 10 1 5 3

8 2 4 6 9 7 10 1 5 3

8 2 7 10

8 2 7 10

2 8 4 6 9 7 10 1 5 3

2 4 8 6 9 1 7 10 3 5

2 4 6 8 9 1 3 5 7 10

1 2 3 4 5 6 7 8 9 10

FIGURE 2 The Merge Sort of 8, 2, 4, 6, 9, 7, 10, 1, 5, 3.

The Merge Sort

We now describe a recursive sorting algorithm called the merge sort algorithm. We will demon-
strate how the merge sort algorithm works with an example before describing it in generality.

EXAMPLE 9 Use the merge sort to put the terms of the list 8, 2, 4, 6, 9, 7, 10, 1, 5, 3 in increasing order.

Solution: A merge sort begins by splitting the list into individual elements by successively
splitting lists in two.The progression of sublists for this example is represented with the balanced
binary tree of height 4 shown in the upper half of Figure 2.
Sorting is done by successively merging pairs of lists. At the first stage, pairs of individual
elements are merged into lists of length two in increasing order. Then successive merges of
pairs of lists are performed until the entire list is put into increasing order. The succession of
merged lists in increasing order is represented by the balanced binary tree of height 4 shown
in the lower half of Figure 2 (note that this tree is displayed “upside down”). ▲

In general, a merge sort proceeds by iteratively splitting lists into two sublists of equal
length (or where one sublist has one more element than the other) until each sublist contains one
element. This succession of sublists can be represented by a balanced binary tree. The procedure
continues by successively merging pairs of lists, where both lists are in increasing order, into a
larger list with elements in increasing order, until the original list is put into increasing order.
The succession of merged lists can be represented by a balanced binary tree.
We can also describe the merge sort recursively. To do a merge sort, we split a list into
two sublists of equal, or approximately equal, size, sorting each sublist using the merge sort