Comp 271 lab 4 - nonrecursive mergesort
Goals
- nonrecursive implementation of mergesort
- more timing comparisions
Update!
Here is MergeBlocks.java.
Implementing mergeblocks() has proven harder than anticipated;
feel free to use this version.
Just take out the mergeblocks() method and paste it in to your version.
Overview
The book has a standard recursive implementation of mergesort (my version is available at mergesort.zip):
- sort each half, recursively
- merge the results
How can this be done nonrecursively? If you examine what is "really
going on" in the recursive version, it all boils down to the following,
sort of in order:
- merge pairs of adjacent single elements to form sorted blocks of length 2
- merge pairs of adjacent sorted blocks of length 2 to form sorted blocks of length 4
- merge pairs of adjacent sorted blocks of length 4 to form sorted blocks of length 8
- ....
One way to describe the loop to sort array A is the following:
blockLength = 1;
while (blockLength < A.length) {
merge pairs of adjacent sorted blocks of length blockLength
blockLength = blockLength * 2;
}
In the IterativeMergeSort starter class I call the "merge pairs of
adjacent sorted blocks ..." method mergepass. You will need a second
array, T (for temp) to do the merges into. For a sample merge
operation, see the merge() method in RecursiveMergeSort. Note that as
you merge pairs of adjacent blocks, you will not be copying back into T
until you've reached the end. Also note that the last block can be
shorter than expected, even of length 0.
After you have implemented nonrecursive mergesort, compare it to
recursive mergesort for a random array of ints of size 1,000,000. Use
nanoTime().
Once you have merged into the array T, you will need to copy the result back into A. A (theoretically) faster alternative is to alternate
use of A and T until you reach a blockLength >= A.length; that is,
for blockLength = 1 you merge from A into T, for blockLength 2 you
merge from T into A, for blockLength 4 you merge from A into T, and
onwards. (If you end up with your data in T, you will have to copy back
into A at that point, but only once.) Implement this for extra credit.
To submit your project, create a zipfile and email it to me at
pld@cs.luc.edu.