As a new and eager employee of Google Tech; you've been asked by your employer to implement a sorting algorithm for inclusion in a package for a lucrative client. However, your boss just wants you to implement one of the simple, quadratic sorting algorithms. To prove that this would be a big mistake, you've decided (on your own) to prove to your idiot boss that it's worth the extra effort to implement one of the O(n log n) sorting algorithms. For this project, you will implement and compare five sorting algorithms:

bubble sort, insertion sort, selection sort, quicksort, and either mergesort or shellsort. Your main program will then do the following:

1. Ask the user for the size n of the list he/she wants to sort.

2. Create an array of size n and fill it with random integers between 1 and n. If n<=100, display the random array on the screen.

3. Run each of your sorts on this array. You must make a deep copy of the array before sorting it, or your second sort will have an easy time of it. Use the System.currentTimeMillis() function to determine the running time of each sort.

4. If n<=100, display the sorted arrays on the screen (they better be the same!).

5. Display the time each sort used to sort the array. Once you have your program working, use it to plot a graph. Have the x-axis represent n, and the y-axis the running time. Use n=10000, 20000, ..., 100000. Plot all sorting algorithms on the same graph (use different colors or line styles). You shall use a spreadsheet program (e.g., MS Excel) or some other program to do this for you. (Will your boss be convinced?)

1. Before you begin programming, sketch a high level design of what you want to implement using the UML notation. At the very least, you should have a use case diagram, class diagram and a sequence diagram.

2. Remember to include comments at the top of your program and 1-2 lines for each function (including pre- and post-conditions).

3. The System.currentTimeMillis() function will return the current system time in milliseconds. Make a call before and after running a sort, then subtract to get the elapsed time. You may need to cast it to type int using (int) System.currentTimeMillis().

4. Use the compareTo() function of the built-in Comparable interface to compare objects in the array, and store your numbers using the built-in Integer wrapper class.

5. Use a random number generator to fill the array.

6. Hint: Use the sample Sorts.java file from the textbook. (provided)