Recursive Sort Programs

apap10.2

Download sort2.cpp. Add the recursive code to the functions QuickSort and MergeSort to make the algorithms work properly. Read the comments in the functions for hints. Test your sort algorithms with the following input data:

size = 100
low = 0
high = 9999
duplicates = yes
show vector = yes

Once your sort algorithms are working, run the program with the following data and keep track of the time for each experiment (run all experiments on the same computer!)

What is happening to the Quick sort? Its times are degrading as the number of duplicates in the list increases. The Merge sort isn't affected by duplicates. Type a double-spaced paper explaining the results received from the above experiments. Also include in your report a description on how the Quick and Merge sort work, and their best and worst attributes.

Turn in the following (in order)

• Cover page: Assignment title, name, date
• Double spaced typed paper
• Timing results from the above experiments. Save the run then print it out.
• Listing of your program

Extra Credit: Rewrite the Quick sort to eliminate this problem with duplicates. Hint: You'll need three partitions, one for less than the pivot, one for equals to the pivot, and the third for greater than the pivot.. Run your new algorithm with the above data.