Implement quicksort and bucket sort. Use the code in your book to help; the partition in quicksort is tricky. Make sure your implementations are correct it is easy to gain some confidence in the correctness of your code by writing a program which creates arrays filled with random numbers, sorts them, and then checks that they are sorted. Then time your code (using System.nanoTime() or similar methods) on both methods for arrays filled with random integers of the following sizes (where n is the number of elements to be sorted, and m is the maximum integer value of the items in the input array): * n is very large, m is very small * n is very small, m is very large * Find values of n and m where both implementations take (approximately) equal time. Discuss where quicksort performs best, and where bucket sort performs best.

A clock time of 0 isn't very meaningful. When timing your code, try doing the same thing many times (like 100 times or more) to get more accurate results. Show both your code and your results. Experiment with the values of m and n and with your code to get reasonable, interesting, reportable results.

Note that the quicksort code in the book is incorrect if you remove the dependence on insertionSort. If you include insertion sort, the code is correct. If you want to eliminate insertion sort, then you should do the following: surround line 27 in quicksort (the "restore pivot" step) with an if block:

 if ((right - left + 1) > 2) { /* 27 */ swapReferences(a, i, right - 1); // Restore pivot }