Anne Dawson: Mergesort.htm

Last updated: Saturday 20th November 2004, 16:34 PT

This document is subject to change without notice.

Please report any errors or omissions in this document:

adawson@coquitlamcollege.com

Mergesort

http://en.wikipedia.org/wiki/Mergesort

http://www.student.seas.gwu.edu/~idsv/idsv.html

http://www.cosc.canterbury.ac.nz/people/mukundan/dsal/MSort.html

The Mergesort algorithm

procedure Mergesort(Array, lowIndex, highIndex)
if(lowIndex  less than highIndex)
    {
        middleIndex = (lowIndex + highIndex) / 2
        Mergesort(Array, lowIndex, middleIndex)
        Mergesort(Array, middleIndex + 1, highIndex)
        Merge(Array, lowIndex, middleIndex, highIndex)
    }

You first find the "middle" of the array or vector.  You sort the first half recursively, then the second half.
A call to Merge then merges the two subarrays into a sorted array.

Merge is a little more involved.
Here's an analogy to what you'll do:

Imagine two stacks of playing cards face up on the table

Each stack of cards is sorted, with the smallest card on top

To merge the two stacks:
        1.  choose the smaller of the two cards on top
        2.  remove from the stack and place face down in a new pile
        3.  repeat until one of the stacks is empty
        4.  take the remaining stack and place those cards face down in your new pile

You now have a sorted pile.

Animation of the Mergesort algorithm:

http://www.student.seas.gwu.edu/~idsv/idsv.html

Example Code:

http://www.coquitlamcollege.com/adawson/mergesort1.cpp

http://www.coquitlamcollege.com/adawson/mergesort2.cpp

http://www.coquitlamcollege.com/adawson/mergesort3.cpp