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

Example-Merge Sorting

 

Sorting algorithms and sorters are covered in detail in Chapter gif. In this section we consider a divide-and-conquer sorting algorithm--merge sort . Given an array of n items in arbitrary order, the objective is to rearrange the elements of the array so that they are ordered from the smallest element to the largest one.

The merge sort algorithm sorts a sequence of length n>1 by splitting it into to subsequences--one of length tex2html_wrap_inline58823, the other of length tex2html_wrap_inline68743. Each subsequence is sorted and then the two sorted sequences are merged into one.

Program gif defines the function MergeSort which takes three arguments, array, i and n. The routine sorts the following n elements:

displaymath68669

The MergeSort routine calls itself as well as the Merge routine. The purpose of the Merge routine is to merge two sorted sequences, one of length tex2html_wrap_inline58823, the other of length tex2html_wrap_inline68743, into a single sorted sequence of length n. This can easily be done in O(n) time. (See Program gif).

   program32974
Program: Divide-and-Conquer Example--Merge Sorting

The running time of the MergeSort routine depends on the number of items to be sorted, n. Although Program gif works correctly for arbitrary values of n, it is much easier to determine the running time if we assume that n is a power of two. In this case, the running time is given by the recurrence

  equation32983

Equation gif is easily solved using repeated substitution:

eqnarray32989

Setting tex2html_wrap_inline68699 gives tex2html_wrap_inline68761.


next up previous contents index

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