Improved Merge Sort by introducing Insertion Sort for array size of below a threshold value because Insertion Sort performs better for less number of elements.
Implement and compare the running times of the following algorithmson randomly generated arrays: (a) Insertion sort, (b) Merge sort (take 1),(c) Merge sort (take 2), (d) Merge sort (take 3). Do not run more than one algorithm in each trial. For Insertion sort, if the running time exceeds 2 min, write the time as infinity. For Merge sort, in each trial, run only one algorithm, for one value of n, 100 times in a loop, and taking the average time. Try the following values of n: 8M, 16M, 32M, 64M, ..., until you get out of memory exception. Submit a report with your observations. Starter code is provide.