As a new and eager employee of NSUTech, Inc. (Nova Southeastern University Technology Incorporated) 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?)