For this assignment, you will be running experiments that empirically test the performance difference between the Mergesort and the Quicksort. In part 2, you will explore whether the invocation of the selection sort for small sizes will improve either of their performance.
Your experiments should test both sorts for at least three array sizes. For each size, run the experiment 100 times, using a new array of random integers each time. Have your program calculate the average and standard deviation over the 100 trials.
Sometimes a divide-and-conquer strategy is more efficient when it invokes a non-recursive strategy once the problem size has been reduced below a specified threshold. Experimentally determine if the MergeSort and the Quicksort benefit by calling a selection sort once the problem size has become small enough. If either of these recursive sorts benefit from using such a threshold, experimentally determine the optimal theshold where one exists.
You will need to type in the implementations for the Quicksort, Mergesort, and selection sort (you may use any of the code presented in class or in the text). You will also need to write code that intializes a vector of integers with random variables. Finally, you will need to design a program that runs your experiments and collects statistics. Randomization and timing tools are provided with the RandGen and Timer classes in the ~miller/cs231/hw3 directory. Also in this directory is a demonstration program that uses these classes.
For this homework, the emphasis is on the report you write, which should describe your experiments, report your results, and draw appropriate conclusions. Your report should consist of two parts and take approximately 2 double-spaced pages. You should also keep your code available for inspection.