| Merge Sort |
12 points
Mergesort is more difficult to understand, and to program, than either bubble sort, insertion sort or selection sort. You should, however, uncover the advantages of mergesort as you do this program.
As you have seen in our activity in class, 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 that uses recursion. Remember that recursion solves a problem by breaking it into smaller, more manageable pieces, which is how mergesort operates.
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 4-word pile "monday saturday tuesday wednesday". This process continues until there is one pile with all the words that were in the original unsorted pile. And the words in this new pile will be sorted.
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 bubble sort. You wrote a bubble sort program either in Java Programming or earlier in this course. The bubble sort program also uses a StopWatch to keep track of how long it takes the bubble sort to finish sorting.
What do you conclude about the efficiency of mergesort vs. that of bubble sort?
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