CS 3343/3341, Merge

CS 3343/3341
Analysis of Algorithms

Divide and Conquer:
Merge Sort

The mergesort is discussed in detail in your text, pages 30-39. (You may have seen this before in the Data Structures course.) Here is your text's top-level view:

Mergesort, in three steps: Divide: Divide the input sequence to be sorted into two equal sized subsequences. Conquer: Sort the two subsequences recursively using mergesort. Combine: Merge the two sorted subsequences to produce the sorted answer.

Mergesort, in three steps:
Divide: Divide the input sequence to be sorted
   into two equal sized subsequences.
Conquer: Sort the two subsequences recursively
   using mergesort.
Combine: Merge the two sorted subsequences to
   produce the sorted answer.

Here is the top level of the book's algorithm:

MergeSort (a, p, r) if p < r q = floor((p+r)/2) MergeSort(A, p, q) MergeSort(A, q+1, r) Merge(A, p, q, r)

MergeSort (a, p, r)
   if p < r
      q = floor((p+r)/2)
      MergeSort(A, p, q)
      MergeSort(A, q+1, r)
      Merge(A, p, q, r)

Click picture or here for full size picture.

Revision date: 2012-02-09. (Please use ISO 8601, the International Standard Date and Time Notation.)