In this lab, you will get practice implementing, modifying and testing the performance of Merge sort.
The basic idea is to take the Merge sort implementation from class and modify it so that its worst-case (and every other case) running time can be described by the recurrence T(N) = 2T(N/2) + O(N), with T(1) = O(1) (I talked about this in class). No matter what, your Merge sort should be fully generic, recursive, optimized for performance and have worst-case running time O(N log N).
There is no required output for this program, but here's what my testbed gives as output:
How many numbers do you want? 10
Populating...done
Print list? y
[27997, 12927, 2420, 16240, 10742, 10387, 28831, 3380, 10399, 7049]
Sorting...done, time=1
Print list? y
[2420, 3380, 7049, 10387, 10399, 10742, 12927, 16240, 27997, 28831]
How many numbers do you want? 1000000
Populating...done
Print list? y
Too many numbers=1000000
Sorting...done, time=324
Print list? n
How many numbers do you want? 2000000
Populating...done
Print list? n
Sorting...done, time=511
Print list? n
How many numbers do you want? 4000000
Populating...done
Print list? n
Sorting...done, time=1124
Print list? n
How many numbers do you want? 8000000
Populating...done
Print list? n
Sorting...done, time=4265
Print list? n
How many numbers do you want? 16000000
Populating...done
Print list? n
Sorting...done, time=5170
Print list? n
How many numbers do you want? quit
The above times are in milliseconds. Basically, do whatever you can do get your myMergeSort method to run as quickly as possible. Timing bonuses may be available, similar to previous labs!
1. Create a new project in NetBeans called Lab4. Make sure you uncheck Create Main Class in the New Java Application window.
2. Within the default package of your Lab4 project, create a new Java class called Lab4.
3. Feel free to use this myPopulateRandomly for testing purposes:
public static void myPopulateRandomly(ArrayList< Integer> inL, int inHowMany) {
inL.clear();
for (int i = 0; i < inHowMany; i++)
inL.add(new java.util.Random().nextInt(Short.MAX_VALUE));
}
Follow the instructions in the Requirements section to see exactly what you have to do for this lab.
Ensure that your implementation of Merge sort satisfies the following technical requirements:
1. Your myMergeSort method must be public static, fully generic, can only take one parameter and should not be recursive.
2. Your recursive method that you use to implement Merge sort should have worst-case running time described by the recurrence T(N) = 2T(N/2) + O(N), with T(1) = O(1). Be sure to give a justification for your recurrence. Keep in mind that the "stan- dard" Merge sort implementation has the slightly more complicated recurrence T(N) = T(FLOOR(N/2)) + T(CEILING(N/2)) + O(N), with T(1) = O(1). We can solve the former recurrencewith iteration, but the latter is trickier. Your implementation of Merge sort must make two recursive calls at each level of recursion, where each recursive call processes the same amount of input (not even off by one).
3. Make as many optimizations as reasonably possible (yes, "reasonable" is a subjective term here).
4. Whenever you instantiate an ArrayList, you need to specify the smallest initial capac- ity that will result in no subsequent expansions. Hint: after you create an ArrayList with a certain capacity, go through and add that many null pointers to it (just make sure you never dereference any of these later). Doing so will ensure that the size and capacity of the ArrayList you just created are equal, so you don't have to worry about getting ArrayIndexOutOfBoundsExceptions when calling set(i, obj).
5. You cannot use any non-final "global" variables that are declared within Lab4 but outside of any method. In other words, no instance variables in Lab4.
6. None of the methods in the final version of your implementation of Merge sort should produce any output. You can produce output for testing purposes, but make sure you delete any / all output statements before final submission.