MergeSort and Quicksort Java code analysis

create a Java class to analyze and compare the mergesort and quicksort algorithms. The sort required is always from smallest value to largest value. Your source code file must be named Sorts.java. Java class methods must match the specifications in the class outline below

1. Create a static Java method, called merge, that merges two sorted lists of integers into a single sorted list

2. Create a static Java method, called mergeSort, that implements a mergesort algorithm that sorts an array of n integers.

3. Create a static partition method that implements the in-place partition algorithm for quicksort

4. Create a static method quickSort that implements the in-place quick sort

5. Create a java method, called isSorted, that tests if an array of integers is sorted in increasing order.

Test your merge, mergeSort, partition, quickSort methods thoroughly to make sure that they are correct; ie they can sort arrays of random values of various lengths. Test your isSorted method too, Make sure to print out the results of the sorts for smaller arrays to visually check that the arrays are sorted.

Experiment #1: Design an experiment to determine which of mergesort or quicksort is the faster sorting algorithm on a on integer arrays of random numbers? Does your answer depend on the size of the array?

Use random arrays of size n, for n = 10, 100, 1000, 10000, 100000, 1000000, 2000000. Use a random number generator to fill your array with integers between 1 and 1000000. For each n, run 20 trials to compare speeds of mergeSort and quickSort. For example, if n = 100, runt mergeSort and quickSort on 20 different arrays of 100 random numbers. For each n, report the number of wins for mergeSort and the number of wins for quickSort. Your program should print out the information to create a table that reports the number of wins for mergeSort and for quicksort as a function of n

Experiment #2 Show that runtimes of mergeSort and quicksort are O(n*log₂(n) ) by timing the runs in Experiment #1 by using the java function System.nanoTime().

Computer printout (from Sort.java main program) that shows that quickSort and mergeSort sort the following array.

{ 34, 67, 23, 19, 122, 300, 2, 5, 17, 18, 5, 4319, -40, 23}

public class Sorts {

//returns true only if a is sorted from smallest to largest values

public static boolean isSorted( int[] a)

/* --------------------MergeSort --------------------*/

//merges sorted slices a[i.. j] and a[j + 1 k] for 0<= i <=j < k < a.length public static void merge ( int[] a int i, int j , int k) { }

//sorts a[ i .. k] for 0<=i <= k < a.length public static void mergeSort(int[] a, int i , int k) { }

//Sorts the array a using mergesort

public static void mergeSort(int[] a ) { }

/* ---------- QuickSort ---------------------------------------------- */

//Implements in-place partition from text. Partitions subarray s[a..b] into s[a..l-1] and s[l+1..b] // so that all elements of s[a..l-1] are less than each element in s[l+1..b]

public static int partition ( int[] s, int a , int b ) { }

//quick sorts subarray a[i..j]

public static void quickSort ( int[] a, int i, int j) { }

//quick sorts array a

public static void quickSort( int[] a) { }

}