Use java only please answer all the questions thank you very much You will create a class called SortTest and all the associated methods necessary to be able to run the following main method.

public static void main(String[] args) { ArrayList testList; final static int ARRAY_SIZE = 10000; testList = new ArrayList(); // fill the ArrayList with gene sequences for (int i = 0; i < ARRAY_SIZE; i++) { testList.add(geneSequence()); } // calculate and display the timing for insertion sort testSpeed(testList, "insertion"); // calcuate and display the timing for mergesort testSpeed(testList, "mergesort"); // calculate and display the timing for the hybrid testSpeed(testList, "hybrid"); }

You will test the speed of these sorts using a mixture of unsorted ArrayLists. Half of the time, the test lists will be completely shuffled - O(n log n) for merge sort but O(n2) for insertion sort. The other half of the time, the lists will be roughly 99.9% sorted (still works with 99.0% sorted, but effects are more dramatic with fewer changed) - O(n log n) for mergesort and O(n) for insertion sort.

1.Implement insertion sort for ArrayList. Feel free to copy/paste whatever example you would like to do this. Note, if you want to make the more general purpose (which is usually a good idea for code reusability) you could read more about Java generics which we will use this semester. In particular, you will replace with > in the function definitions. Consider this optional.

2.Also implement merge sort for ArrayList. For the purposes of this assignment, be sure to use a version of merge sort that is O(n log n) and not O(n) for sorted lists. Feel free to copy/paste whatever example could you would like to do this.

3.Implement a hybrid sort, which tests to see if the array may be nearly sorted already. If it is, sort it with insert sort (O(n)), if not, use merge sort (O(n log n)). A few possible heuristics you could use:

a. Pick the first X values, and check to see if Y of them are in increasing order.

b. Pick X evenly spaced values throughout the array and see if Y are in increasing order.

c. (basically, anything that works in O(1) time)

4. Run the main method. Document the output for all three sorts. Do you see the hybrid working better on the whole test set compared to each one separately? This is what we aiming for, but it isnt necessary to turn in the assignment.