Data Structures and Algorithms with Object-Oriented Design Patterns in Java

Merge Sorting

The fourth class of sorting algorithm we consider comprises algorithms that sort by merging . Merging is the combination of two or more sorted sequences into a single sorted sequence.

Figure illustrates the basic, two-way merge operation. In a two-way merge, two sorted sequences are merged into one. Clearly, two sorted sequences each of length n can be merged into a sorted sequence of length 2n in O(2n)=O(n) steps. However in order to do this, we need space in which to store the result. That is, it is not possible to merge the two sequences in place in O(n) steps.

Figure: Two-way merging.

Sorting by merging is a recursive, divide-and-conquer strategy. In the base case, we have a sequence with exactly one element in it. Since such a sequence is already sorted, there is nothing to be done. To sort a sequence of n>1 elements:

Divide the sequence into two sequences of length and ;
recursively sort each of the two subsequences; and then,
merge the sorted subsequences to obtain the final result.

Figure

illustrates the operation of the two-way merge sort algorithm.

Figure: Two-way merge sorting.