java

Part A: Implement the insertion sort algorithm discussed in the lectures. Part B: Implement the merge sort algorithm discussed in the lectures. Part C: Test the sorting algorithm as follows. For input sizes n = 5,000, n - 10,000, n = 15,000,..., n = 100,000 Create an array Ais of size n. Fill the array with n random integers. Create a copy of the array, Ams. Pass the array Ais to your insertion sort and record the number of comparisons. Pass the array Ams to your mergesort and record the number of comparisons. Then produce a graph which shows for each value of n, the number of comparisons for each sort You should also plot n log n and n on the same graph to compare their shape with the insertion sort and mergesort results