For this assignment, you will compare the performance of various sorting algorithms. In order to time the different sorts, a StopWatch class has been provided for you. This class models a simple stopwatch, which you can start before executing a piece of code and then stop afterwards to measure the elapsed time. For example:

1. (40%) Write a class named SortTimer with a main method that does the following:
   • Prompt the user for a list size (e.g., N = 10,000).
   • Create an ArrayList of the Integers from 1 to N, in random order. Note that you can do this by first putting the numbers in the list in order, then calling Collections.shuffle on that list.
   • Create a stopwatch and use it to time the execution of the Collections.sort method on your list.

   Note: a text-based interface is fully sufficient here. For up to 5 extra credit points, you can create a graphical user interface that is more attractive and easier to work with.
   
   

2. (20%) Using your SortTimer class, measure the performance of Collections.sort on lists of increasing sizes. Since the timings provided by the StopWatch class are somewhat imprecise (they can be affected by garbage collection and other tasks sharing the CPU), you will want to do several executions at each size to account for variation. For example, you might produce a table of results similar to the following (which contains purely fictional data):

   list size	execution 1	execution 2	execution 3
   10,000	200	240	200
   20,000	320	340	350
   40,000	500	500	500
   80,000	900	1000	950
   160,000	2100	2000	2000

   Depending on the speed of your computer, you will need to select file sizes that produce timings that are reasonably differentiated. You will also need to continue increasing the file size until the performance pattern stabilizes.

   Report your timing data. Do your timings support the claim that the Collections.sort algorithm uses an efficient O(N log N) sort? Justify your answer.
   
   

3. (10%) Static methods for performing selection sort and merge sort are provided in the in Sorts class. Similar to how you measured the performance of Collections.sort in the previous problem, measure the performance of selection sort. As before, you will need to select appropriate sizes and increase the sizes until the performance pattern stabilizes.

   Report your timing data. How do these timings compare in absolute terms with Collections.sort on lists of equivalent sizes? Do your timings support the claim that the selection sort is an O(N²) sort? Justify your answers.
   
   

4. (10%) Similarly, measure the performance of the merge sort algorithm and report your timing data. How do these timings compare in absolute terms with Collections.sort and selection sort on lists of equivalent sizes? Do your timings support the claim that the merge sort is an O(N log N) sort? Justify your answers.
   
   
5. (20%) As we discussed in class, big-Oh characterizes the efficiency of an algorithm in the long run. It is certainly possible that the constants and high overhead of an O(N log N) algorithm can make it slower than an O(N²) algorithm on small problems. Modify the merge sort code in the Sorts class so that selection sort is used when list size becomes small. For example, if the recursion in merge sort gets down to a list of size 5, you could avoid further recursion and simply call selection sort to handle the rest. The threshold for switching to selection sort should be a constant, defined at the top of the Sorts class (so that it is easy to find and change, if desired).

   Time your modified merge sort on a large list and compare its performance relative to the standard merge sort. Does switching to selection sort at size 5 improve overall performance? Is there an optimal threshold that produces the best performance? Report your data and provide explanations to support your claims.

Turn in your SortTimer and modified Sorts classes, along with your timings and commentary.