Write a program in C++ 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 50,000, 500,000, and 5,000,000.  For each array size, record the time required for the sorts.