SORTING ALGORITHMS C++

Implement Problems 1, 2 and 3, each in a separate program. Problem 1: Comparing 4 Sorting Methods Merge Quick Bubble Selection Write a program that creates an array of randomly generated integers (in the range 1 to 100000) and uses four sorting algorithms to sort them. It must record or print the time taken (empirical result) by each sorting method to sort the same array. In order to make a meaningful comparison and analyze the time taken by the four algorithms with their theoretical time complexity (or growth rate) the program must produce several sets of empirical results. To do so, you must run the program several times, each time with a different input array, both by increasing its size and changing the randomly generated integers. 1) CORRECTNESS OF THE IMPLEMENTATIONS: Your program must output results that would clearly illustrate that your implementations are correct. So write a Test program to call each sorting method and output the array before and after each sorting method is called. Use a smaller array of size 10 to test the correctness. 2) EMPIRICAL RESULTS: • Next, run the program for several randomly generated arrays. Each time print only the time taken by each sorting method to sort each array. Run the program at least 40 times with 40 different arrays of random integers. • Choose the number of integers (size of the input) in the first set to be large enough to get a time that is larger than zero. Increase steadily the size of the array in the remaining sets in a way that will show a significant increase in the time taken to sort them. • Once an array of integers has been generated, sort that array using the 4 different sorting methods. To make a valid comparison of the times taken by the four methods you must use the same unsorted array for each sorting method. So use the following code: