1 Introduction In this homework, you will implement three sorting algorithms, and then test their efficiency (running time). This assignment will consist of not only coding, but also testing your code on large data set. The three sorting algorithms to implement are Merge Sort, Quick Sort and Radix Sort. Note that to realize Radix Sort, a function of counting Sort by digits is needed to be implemented firstly. 2 Instructions The following files have been given to you: 1. A C++ header file (SortHelper.h) declaring a namespace SortHelper of functions. 2. A C++ source file (main.cpp containing a main function with tests. Download the files on blackboard. In Sort Helper.h, there are several functions which are creating a data set of the given size, measuring the running time of any given function in milliseconds, checking whether the array is sorted, etc. In main.cpp, you need to implement the three sorting algorithms and test the efficiency of each sorting function. Please read the instruction in the main.cpp carefully. Efficiency Test: After you have correctly implemented the sorting algorithms, executing the main func- tion, you will see how long each sorting function takes to run on both random and sorted inputs. Please test each algorithm on both random and sorted input of different sizes: 5000, 10000, 25000, 50000, 75000, 100000, 250000, 500000, 750000 and 10000000. You will get a list of running time in milliseconds. (The timing() function in Sort Helper is to test the speed of an given function.) 3 What to submit You need to submit the following files via blackborad. 1. A C++ source file (main.cpp containing a main function with tests. 2. A pdf file contains a table of running times for three algorithms on random and sorted arrays of sizes 5000, 10000, 25000, 50000, 75000, 100000, 250000, 500000, 750000 and 10000000, and two charts to statistic the efficiency. The first chart is for running times of three algorithms on random arrays of the above different sizes, while the second chart is for sorted arrays. In addition, your observation, discussion and comments about the efficiency should be included. 1 Introduction In this homework, you will implement three sorting algorithms, and then test their efficiency (running time). This assignment will consist of not only coding, but also testing your code on large data set. The three sorting algorithms to implement are Merge Sort, Quick Sort and Radix Sort. Note that to realize Radix Sort, a function of counting Sort by digits is needed to be implemented firstly. 2 Instructions The following files have been given to you: 1. A C++ header file (SortHelper.h) declaring a namespace SortHelper of functions. 2. A C++ source file (main.cpp containing a main function with tests. Download the files on blackboard. In Sort Helper.h, there are several functions which are creating a data set of the given size, measuring the running time of any given function in milliseconds, checking whether the array is sorted, etc. In main.cpp, you need to implement the three sorting algorithms and test the efficiency of each sorting function. Please read the instruction in the main.cpp carefully. Efficiency Test: After you have correctly implemented the sorting algorithms, executing the main func- tion, you will see how long each sorting function takes to run on both random and sorted inputs. Please test each algorithm on both random and sorted input of different sizes: 5000, 10000, 25000, 50000, 75000, 100000, 250000, 500000, 750000 and 10000000. You will get a list of running time in milliseconds. (The timing() function in Sort Helper is to test the speed of an given function.) 3 What to submit You need to submit the following files via blackborad. 1. A C++ source file (main.cpp containing a main function with tests. 2. A pdf file contains a table of running times for three algorithms on random and sorted arrays of sizes 5000, 10000, 25000, 50000, 75000, 100000, 250000, 500000, 750000 and 10000000, and two charts to statistic the efficiency. The first chart is for running times of three algorithms on random arrays of the above different sizes, while the second chart is for sorted arrays. In addition, your observation, discussion and comments about the efficiency should be included