1.Write a c++ program that can be used to compare Insertion Sort, Merge Sort and Quick Sort.

Your program must:

Read an array size from the user, dynamically allocate an array of that size, and fill the array with random numbers.

Make two additional copies of the random array.

Sort the arrays with the Insertion Sort, Merge Sort and Quick Sort algorithms studied in class, doing a time-stamp on each sort.

If the array size is less than 100, print the array contents before it is sorted and after each sort (use this to debug your sort functions).

Use your program to measure and record the time needed to sort random arrays of size 75,000, 750,000, and 7,500,000. For each array size, record the time required for the sorts.

2.Write one or two paragraphs analyzing the times that you recorded and clearly stating your conclusions regarding them. Be sure to give the big-O efficiency of all three algorithms and to clearly state when Insertion Sort is most efficient, when MergeSort is most efficient and when QuickSort is most efficient.

Show step-by-step how Insertion Sort, Merge Sort and Quick Sort would sort the data shown below into ascending order. Assume that the QuickSort algorithm uses the first element pivoting scheme discussed in class. Clearly and neatly show and label all work. No credit will be given if work is not shown.

You may hand-write this part of the assignment and take a picture or type it. Submit the file in the D2L drop box by the due date shown in D2L.

39 23 64 27 75 14 50 41 32