Implement and compare the running times of the following algorithms on 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 provided.