Harvey Mudd College
Computer Science 60
Assignment 11, Due Thursday, December 2, by midnight
Algorithmic Complexity via Sorting
Mergesort in Java and Empirical Complexity Analysis
For this problem, you will write the mergesort algorithm in Java and then test
its running time empirically in order to validate that it runs in
n*log(n) time, rather than O(n) or O(n^2).
Files to create/modify
You will want copy the Mergesort.java file in
/cs/cs60/assignments/a11.
In that file, you will find a simple linked list class (with the
ability to generate long lists of "random" floating-point numbers
between 0.0 and 1.0.
The file you submit will be the Mergesort.java file, with
the code for mergesort inserted into the
Mergesort class, and a table of running times vs. problem
sizes (see the model table below) within a java comment.
Part 1: coding mergesort
The skeleton provided in Mergesort.java has a placeholder (that
currently does nothing) named mergesort as follows:
static List mergesort(List list)
{
return list;
}
You will need to fill in code that implements mergesort using the
simple List class provided. We are not using the Java LinkedList
class in order to be certain of the operations being performed
in each step through the algorithm.
Also, because the fast running time of
mergesort requires that duplicate data not be created,
you need to follow these guidelines:
- Do not use the constructor for the List class, except
to create the initial list filled with "random" values.
- Do not allocate or use any more space than necessary.
That is, you can allocate new lists, but may not copy
lists. (A new list is merely the size of one cell, but
copying a list could potentially be very costly.)
- Do modify the list passed into mergesort by manipulating
the reference links that comprise the list. Basically, you
are taking advantage of side effects to save space and time.
- Use the List class as it it were a private, inner class
of Mergesort.
- You should perform three steps in your mergesort
algorithm:
- Split of the input list into two almost-equal halves
A good way to do this is to create two new lists and
add pointers alternatively to each from the original.
See the picture below for an illustration.
Feel free to add the pointers in reverse order, if you
like (this actually makes the split easier to code).
- Recursively sort the two lists.
- Merge the two sorted lists back into a final list that
gets returned.
- Notice that the above guideline performs a split, then a sort,
then a merge step. The rex code provided in the notes "skips
over" the initial split (with a call to map), but it's important
in the Java implementation.
Be sure you test your code so that you know that mergesort is
working before going on to the empirical analysis of its running
time (the next part of the problem).
Here is the illustration of one way to split a linked list.
Part 2: analyzing mergesort
For this part, you will need to add code to test your working
mergesort algorithm (from Part 1) on lists of various sizes.
You should create a table of the following form. The three columns
list the running time of your mergesort algorithm divided by
N, Nlog(N), and N^2, respectively, for
the various list lengths (N) shown to the left. Note that
T(N) represents the actual running time of your
mergesort algorithm (in milliseconds) on a list of size N.
Inside the skeleton Mergesort.java file is code which
will output the running time of your program. It outputs the wall clock time, not
the processor time, but it should be a good enough approximation to use.
T(N) T(N) T(N)
list ----- ------- -----
length (N) N Nlog(N) N^2
N = 512
N = 1024
N = 2048
N = 4096
N = 8192
N = 16384
N = 32768
N = 65536
N = 131072
N = 262144
N = 524288
N = 1048576
Note that writing the code to get these times is up to you, but
that you only need to run mergesort on each list length once.
Once the table has the above values filled in (within a
comment in your Mergesort.java file), briefly comment
on the progression of those values in each column as the length
of the list to be sorted increases.
Reading
Complexity and its analysis is covered in Chapter 11 of the text.
Submission
You should submit your Mergesort.java source file in the usual
way, i.e., by running
% cs60submit Mergesort.java
You will be asked to input the assignment number (11).