Discrete Mathematics for Computer Science

Merge Sort 571

rnMerge Sort

Sorting algorithms not only are studied in a variety of computer science courses but also

are used as an important processing step in many applications. The merge sort algorithm

examined here uses a divide-and-conquer strategy. The idea is to divide the original set

of elements in half, complete the sorting process for each half of the set, and then merge

these two smaller sets, forming a sorted version of the original set. The order of worst-case

complexity of this sorting algorithm is as good as that of any sorting algorithm that only

uses comparisons between pairs of elements as a measure of complexity. After presenting

an algorithm for this process and showing that it is correct, we find a recurrence relation

that describes the complexity of the algorithm. Finally, an example will be given that shows

how the algorithm works.

INPUT: An array A with N elements

OUTPUT: The elements of A are sorted in nondecreasing order

MergeSort (A, 1, N) /* The initial call */

MergeSort (A, Left, Right) /* The recursive procedure */

if (Left < Right) then

Midway = [(Left + Right - 1)/21

MergeSort (A, Left, Midway)

MergeSort(A, Midway + 1, Right)

Merge(A, Left, Midway, Right)

9.8.1 Correctness

A proof by induction shows that this algorithm is correct. For an array with one element, the

condition Left < Right is false, so the procedure terminates. Certainly the single element

is returned in sorted order. Now, assume the procedure is correct for all arrays with fewer

than N elements, and show that the procedure is correct for an array with N elements.

Since Left < Right is true, the procedure is executed on two arrays of size less than N.

By induction, the procedure is correct on such arrays. Now, assume Merge is correct, so

the two sorted sublists will be merged to form a sorted version of the original array of N

elements. Therefore, by induction, MergeSort is correct for arrays of any size N.