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.
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).