• Task 1: It is known that when the size of a sorting problem is small, then insertion sort works best. This idea can be used in merge sort and quick sort: For a recursive call, at first, check if the size of a subarray is less than 1000, use insertion sort instead. Suppose merge sort and quick sort with this idea are implemented in methods called mergesort2 and quicksort2.

  Please create a method called task1, which compares the performances of four methods, i.e., mergesort, mergesort2, quicksort, and quicksort2, on the same set of 100 random arrays of size 1,000,000. The method task1 will create these 100 examples and summerize the running time for each method. Based on the experimental results, draw your conclusions.

• Task 2: For many inputs, testing if a subarray is already sorted can speed up quicksort. In this task, please implement the following method which checks if the subarray of the array arr (from low to high, inclusive) is already sorted:
  public static boolean isSorted(int low, int high)
  Using isSorted(low, high) in quicksort as follows: At the beginning of the recursive call, check if the subarray is already sorted. If yes, exit doing nothing; otherwise, continue as usual. Implement this idea in quicksort and quicksort2, and let us call the resulting two methods as quicksort3 and quicksort4, respectively.

  Please create a method called task2, which compares the performances of four methods, i.e., quicksort, quicksort2, quicksort3 and quicksort4, on the same set of 10 random arrays of size 1,000,000, plus 10 copies of sorted and reversely sorted arrays of size 10,000,000. The method task2 will create these examples and summerize the running time for each method. Based on the experimental results, draw your conclusions.

• Task 3: It is known that the qualify of pivots in quicksort affects the performance of quicksort. Please experiment these two ideas in quicksort:
  • One uses the median of the three elements, i.e., first, middle, and last, as pivot for partition.
  • One first selects 9 elements equally spreading out in the array, inclduing the first and the last element. Compute the median of the first three, the median of the next three, and the median of the last three. Then use the median of three medians as pivot.
  Based on the best quicksort method from Task 2, create two new methods, called quicksort5 and quicksort6, such that quicksort5 uses the first idea and quicksort6 uses the second idea for picking pivots.

  Please create a method called task3, which compares the performances of five methods, i.e., heapsort, quicksort, quicksort5, quicksort6, and the quicksort method used as the base for quicksort5 and quicksort6, on the same set of arrays of size 1,000,000, including 10 copies random arrays, 10 copies of reversely sorted arrays, and 10 copies of organ-pipe shaped inputs (the first half is from n/2 downto 1 and the second half from 1 to n/2, where n is the size of the array). The method task3 will create these examples and summerize the running time for each method. Based on the experimental results, draw your conclusions.

  On www.sorting-algorithms.com, the illustration shows that heapsort is often the winner for reversely sorted arrays. Do you agree or disagree? Draw your conclusion with justification.

• Task 4: On www.sorting-algorithms.com, it says that "insertion sort is the clear winner" on nearly sorted arrays. There are at least two types of "nearly sorted" arrays: k-exchanges and k-distance, where k is an integer. An array is called a k-exchanges array if the array becomes sorted by performing at most k exchanges. For example, sorting.java uses 100-exchanges for nearly sorted arrays. An array is called a k-distance array if, for each element, the distance from its initial position to its position in the sorted array is no more than k. A k-distance array can be created from a sorted array by randomly shuffling each subarray of size k. www.sorting-algorithms.com uses 1-distance for nearly sorted arrays.

  Please compare the performances of quicksort (choosing the best quicksort you have), heapsort, mergesort, natural mergesort, and insertion sort on k-exchanges and k-distances arrays for various k values. You will create a method called task4, which takes k = 10, 20, 40, 80, 160, 320, create 100 k-distance arrays of size 5,000,000, run in turn the chosen sorting methods on each array, and collect running times. Then for k = 100, 200, 400, 800, 1600, 3200, create 100 k-exchange arrays of size 5,000,000, run in turn the chosen sorting methods on each array, and collect running times. Based on the collected running times, draw your conclusion with justification. Is your conclusion consistent with the conclusion of www.sorting-algorithms.com?

Please submit your modified code, including your conclusions and a transcript of its execution, in the ICON dropbox for Project 3 before the deadline.

Finally, a note on cmputing time. Today's computers run fast. If you run on a small input, the computing time is too small to tell the difference. However, not everyone can easily access a fast computer. If one sorting job takes more 10 minutes, you may stop it from running and use a smaller input. Please document this in your report.

Thank you!