Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

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 gif 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. I.e., it is not possible to merge the two sequences in place in O(n) steps.

   figure42842
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:

  1. Divide the sequence into two sequences of length tex2html_wrap_inline58823 and tex2html_wrap_inline68743;
  2. recursively sort each of the two subsequences; and then,
  3. merge the sorted subsequences to obtain the final result.
Figure gif illustrates the operation of the two-way merge sort algorithm.

   figure44016
Figure: Two-Way Merge Sorting




next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.