Description
(1) [60 points]
Implement the insertion sort and merge sort algorithms with any programming
language you choose and run them with input number lists. Generate the list elements
with a random function and increase the list size incrementally until you find the
execution time of your merge sort program is consistently shorter. Draw the two curves
in a figure (execution time vs input list size) about the two programs. Using the example
to discuss why the asymptotic analysis is meaningful. Attached program codes in your
submission.
(2) [40 points] Problem 2-1 on Page 39 of the CLRS textbook.