Merge sort
Like quicksort, merge sort uses recursion.
The basic idea is as follows:
- divide the array at its midpoint, and
recursively apply merge sort to both halves.
- make a single pass through both halves (which are now sorted),
and merge them into one sorted whole.
Here's a demonstration of merge sort. If you need instructions on
running the demo, look here.
The algorithm starts with an array of random numbers. Each number is
represented with a vertical stick. The height of the stick indicates
the value of the number, and its left-right position indicates its
location in the array. Click on "Run" to start the demo.
Look for partially-sorted portions of the array, which result from
recursive calls to merge sort. Look also for the double pass through
two portions of the array, after which the two portions are merged.
Alejo Hausner, CS Department, Princeton University
Last modified: Tue Jul 23 14:10:09 1996