1. Use class Sort.java provided in class, the dual-pivot Quicksort of Java 8 (Arrays.sort), and RadixSort.java provided in class.
2. Do the following for Mergesort, Quicksort, Heapsort and dual-pivot Quicksort:
a. Create 100,000 random keys (of type long) and sort them. Repeat this 100 times.
b. Compute the average CPU time taken to sort the keys for the four methods.

c. Comment on the results and compare them to the average-case complexities discussed in class.

As we discussed in the class, all these sorting algorithms I used for testing have the same average-case complexities with O (n log n). But the data I got which shows in the upper diagram illustrate that Quick sort is the most fast sorting method especially when you need to sort a large amount of data.
Dual-pivot quicksort is also fast than merge sort and Heap sort. Heap sort can be used when the pending data between 1000-1000, 000, and for Merge sort is the first choice when there are more than 1M data.
3. Do the following for the four sorting methods of #2, and for Radix sort:
a. Create 100,000 random strings of length 4 and sort them using the five sorting methods.
b. Repeat (a) 10 times Compute the average CPU time taken to sort the keys for the five methods.

c. Repeat (a) and (b) with strings of length 6, 8, 10.

d. Create a table with the results and compare the times with the average-case and worstcase complexities as studied in class.
The length of string is 4:

The length of string is 6:

The length of string is 8:

The length of string is 10:

The upper diagrams and tables show that when the length of string changed, the total using time of five kinds of different sorting methods are diverse. And we can see that when string’s length is 4, Radix sort used the least time to sort 100000 random strings while Heap sort was the lowest. But as the length of string increasing, the property of Radix sort became lower and when the length of string was over 8, it was the slowest sorting algorithm.

As we discussed in the class, the average cases of the other four sorting methods are O (nlogn) except Radix sort. Radix sort can run in O (nlogn) only when the value of d is log (n) and N = O (n). The worst case of this sorting method is O (d (n+N)) and for Quick sort is O (n*n) while Merge sort and Heap sort are stabilizing with the worst-case running time of O (nlogn).
4. Comment on: which sorting method will you use in your applications? in which case? Why? Here we mainly tested on four kinds of sorting methods: Mergesort, Quicksort, Heapsort and dual-pivot Quicksort. As the data analysis did for test result, the time complexity of the Mergesort is O(nlogn) and the space complexity is O(n); the best time complexity of the Quicksort is O(nlogn) and the worst is O(n^2), the space complexity is O(nlogn); the time complexity of the Heapsort is O(nlogn) no matter in best case or the worst case; the time complexity of the dual-pivot Quicksort in best case is O(nlogn) and O(n^2) in the worst case.

Actually there are also many other kinds of sorting methods such as Selectionsort, Insertsort, Bubblesort, Radixsort and ChainRadixsort. As different methods have unequal features, I will select an optimum method according to various circumstances. Personally, when n is small, I will prefer to use insertsort or Selectionsort; when n is large, I will choose Heapsort or Mergesort; when n is large but the keys have few bits, ChainRadixSort is my first choice; when all data are mainly in order, Insertsort or Bubblesort is better to save time, and Quicksort is best for the unordered data.
In a word, Mergesort, Bubblesort, Insertsort and Radixsort are the stabilized sorting methods. Quicksort, Heapsort and Mergesort have the time complexity with O(nlogn), and both Heapsort and Mergesort have the same time complexity with O(n^2) no matter in the best case or the worst case.
5. Create a simple array.
a. Write a method that creates an array of size 10 and insert one million integers by using the incremental strategy.

b. Write a method that does the same as (a), but uses d-tupling; that is, it increases the size of the array by d*N.

c. Test your program of (a) for values of c = 10, 50, 100, 200, 500, 1000, 2000, 5000 and 10000. Do the same for (b) for values of d = 1.2, 1.4, …, 3.8, 4.0. Record the CPU times for each case and draw a table.

d. Comment on the results obtained… which strategy will you use. Which value of d will you choose? Why?
As we can see from the data gained before, two strategies have different properties when the variant change. For me, I prefer to use d-tupling when insert integers into an array with an initial value as this strategy is more fast, more flexible and easy to implement. What is more , as the data I got, when the value of d is 3.2, total using time is the least, so I will initialize d’s value of 3.2.