Comp 271 lab 3 - iterative mergesort

A Race of Sorts

Overview

Bailey implements a recursive version of mergesort. You are to implement the non-recursive version.

I've provided you with a BlueJ project named sorters (as sorters.zip). In the Sorters.java class in this project, I implement most of the sorting methods of Bailey chapter 6, each applied to a class IntList which is my own implementation of an ArrayList<int>.

In particular, recursive mergesort appears as IntList.rmsort(). This would sort an array of length 100 by:

Iterative mergesort works differently. At any one time, you visualize the array as a sequence of "blocks", each of size a perfect power of two except for the final block. At the start, the blocksize is 1, and each block of length 1 is, of course, sorted. The process repeats with successive block sizes 2, 4, 8, 16, 32, ... until the blocksize becomes larger than the entire array size. On an array of size 100 you would now do the following:

I've supplied you with the following merging methods:

T is the temp space, to be allocated at the start of imsort(). The first merger method, mergeblocks(), merges two equal-sized blocks; the second allows for the block sizes to be unequal. Use whichever you prefer. Both should handle having an undersized block as the last block of the array, but let me know if you have problems.

In class Sorters.java I've started the implementation of iterative mergesort in method imsort(). The code there is this:

    public void imsort() {
        int[] temp = null;  // allocate temp; finish this!
        int blockLength = 1;
        while (blockLength < elements.length) {
            //mergepass(...)
            // swap elements and temp as follows:
            //int [] a = elements;    // this is just a pointer, not an allocation!
            //elements = temp;
            //temp = a;
            blockLength *= 2;
        }
    }

You will have to edit this as necessary, and also edit the mergepass() code. You should not change the mergeblocks() methods. Make sure you allocate temp!

My class SortTester runs several versions of sorting algorithms on the same data, and records the time. Currently it runs InsertionSort, recursive MergeSort (Sorters.rmsort()), and Java's built-in Collections.sort(). You are to complete the definition of iterative mergesort, imsort(), and test it for speed against recursive mergesort and Collections.sort(). You will need to comment out the InsertionSort test once you've got imsort() working, as you'll need to test it with sizes much too large for InsertionSort to handle in a reasonable time.


In my definition of class IntList, I've left out the expand() method (the topic of the previous lab), but you don't need that as you're not using add(). Instead, you will create IntLists of the desired size using the constructor,

    IntList A = new IntList(100000);

and then use A.RandomFill() to create random entries. My code does that, and then makes copies of the data, so that different sorts all start with the same initial data. Currently the code runs InsertionSort on nums (this is the one you will comment out), recursive mergesort on nums1, and is set up to run iterative mergesort on nums2. After you run your sort method, you can check that it worked with IntList.checksort(). Right now, this fails for nums2, because imsort() isn't finished.


Timing Comparisons

First, try comparing selection sort and insertion sort for sizes up to about 100,000.

Then comment out selection sort and try for block sizes of 1,000,000 up to 10,000,000.

Finally, find out how large an array you can sort with mergesort in 10 seconds. Does the timing seem to fit the O(N log(N)) model?

Make sure you use checksort() to verify that your sort implementation works. I will.

To submit your project, create a zipfile and email it to me at pld@cs.luc.edu, or use sakai. It might be easiest simply to upload SortTester.java and Sorters.java (for this project I will need both).