# Algorithms

Algorithms Problem

Modify the code sorting.java to fulfil the following requirements.

Problem 1: Implement the bottom-up merge sort as presented in Chapter 1. Compare the performances of the bottom-up merge sort and the standard merge sort on the same set of examples: 100 instances of 1,000,000 intgers, 100 instances of 2,000,000 intgers, and 100 instances of 4,000,000 intgers, respectively, in the two ranges of [1..1,000] and [1..1,000,000]. Give a summary on the average performances (both computing time and number of comparisons) of these two sorting algorithms and draw your conclusion.

Problem 2: Experiment the following two ideas in Merge Sort and Quick Sort:
Implement the following method which checks if the subarray of the array arr (from low to high, inclusive) is already sorted:
private static boolean isSorted(int low, int high)
Using isSorted(low, high) in merge sort and quick sort as follows: At the beginning of the recursive call, check if the subarray is already sorted. If yes, do nothing; otherwise, continue as usual.
At each recursive call, if the size of a subarray is less than 100, use insert sort instead of merge sort or quick sort.
To identify an idea is useful or not, for each sorting algorithm, you have four versions to test: (a) use both ideas, (b) use first idea; (c) use second idea; (d) use none. Compare the performances (run time only) of these eight versions of the algorithms on the same set of examples as in the previous problem and draw your conclusion.

Problem 3: Please experiment the following idea in the best quicksort algorithm from Problem 2:
one uses the median of three elements, i.e., first, middle, and last, as pivot for partition.
Using the same set of examples in Problem 1 to see the impact of this idea, along with the following sorting algorithms: the java built-in Arrays.sort, heapsort, the best version of merges sort from Problem 2, and the best version of quicksort from Problem 2. Give a summary on the average performances of these five algorithms and draw your conclusion.

Problem 4: On www.sorting-algorithms.com, it says that “insertion sort is the clear winner” on nearly sorted arrays. Please compare insert sort with the best quick sort algorithm from Problem 2 on the same set of nearly sorted examples: 100 instances of 2,000,000 nearly sorted intgers with no more than 100 inversions in the three different ranges: [1..10,000], [1..100,000], and [1..1,000,000], respectively. Give a summary on the average performances of these two sorting algorithms and draw your conclusion with justification.

Problem 5: On www.sorting-algorithms.com, the illustration shows that heapsort is often the winner for reversed initial order arrays. Please compare heapsort with the best quick sort algorithm from Problem 2 on this type of input arrays. You need to create arrays of reversed initial order for your experiment which runs on the same set of 100 arrays of size 2,000,000, and draw your conclusion with justification.

PLACE THIS ORDER OR A SIMILAR ORDER WITH US TODAY AND GET A GOOD DISCOUNT