Merge Sort

16 points

Mergesort is more difficult to understand, and to program, than either bubble sort or selection sort. You should, however, uncover the advantages of mergesort as you do this program.

As you have seen, mergesort works by first breaking the words (or whatever is being sorted) into smaller and smaller "piles". When the sort method in mergesort receives a "pile" (an array, really) of words, it asks, "Can I break this pile into two smaller piles?" If this can be done, the sort method divides its pile of words into two smaller piles, creates two new instances of the sort method, and passes one of the smaller piles to each new sort method. The process then starts over again with the just-created sort methods. This is recursion in action. So we are working on a sorting approach and practicing recursion. Remember that recursion solves a problem by breaking it into smaller, more manageable pieces.

The piles of words can no longer be broken into smaller piles when there is 1 word in each pile. What happens next is that the direction of the program reverses, and small piles are combined into larger and larger piles. This is done in the merge method. What happens when merge is called and each pile has 1 word in it? If the word "tuesday" is in one pile and "wednesday" is in the other pile, after merge runs there will be one pile with the contents "tuesday wednesday". If this 2-word pile is then combined with another 2-word pile with the words "monday saturday", the result will be the larger pile "monday saturday tuesday wednesday". This process continues until there is one pile that has as many words as the original pile did. And the words in the pile will be in sorted order.

Once you have your mergesort program working, study how long it takes to sort different numbers of words. Try sorting 100, 1000, 10,000 and 50,000 words.

Then compare the efficiency of mergesort to the efficiency of insertion sort. You wrote an insertion sort program earlier in this course.

What do you conclude about the efficiency of mergesort vs. that of insertion sort?

 

Starting Point

You can download MergeSort.java, MergeSortTest.java and StopWatch.java to use as starting points in writing your program. Instructions for writing the two classes are given in the .java files. StopWatch.java is complete. The data file with the unsorted words is list.dat.