Data Structures and Algorithm Analysis C++

Write a program to verify your solution to Exercises 7.17. Your program should randomly generate three integer arrays of N=10³, 10⁵, and 10⁷ elements and run either merge sort or insertion sort to sort the arrays in increasing and decreasing orders. Then run both insertion sort and merge sort on the three ordered and three reverse-ordered arrays and output the numbers of comparisons and assignments performed between elements of the input arrays during the executions of the two sorting algorithms on each of the arrays. Draw a table to summarize the outputs of your program on the six input arrays (3 ordered and 3 reverse-ordered) and discuss about whether the performance of the insertion sort and merge sort on those ordered and reverse-ordered arrays is consistent with your solution to Exercise 7.17. If not, why?

Determine the running time of mergesort for a. sorted input b. reverse-ordered input c. random input 7.17