Preamble

In this lab you will write a C++ program that implements and tests three sorting algorithms. You must implement these yourself without linking any external libraries. Your lab should be             completed in a single cpp file called lab1.cpp, and should compile at the command line in replit very simply as follows:

g++ -o lab1 lab1.cpp

Please do not submit labs that don’t compile. I will not debug syntax errors when marking.

Lab Description

We’ve done a lot of hand-waving about O(n2 ) sorting algorithms being faster than O(nlogn) sorting algorithms when the problem gets below a certain size. In this lab, we will put such claims to the test. You will implement three sorting algorithms:

First, implement standard, out-of-the-box Selection sort and Merge sort. Each should be in       their own function(s). An unsorted array goes in and gets sorted. Sorting should be done on the original array (do not return a new one). Implementation details beyond that are up to you.

Next, implement a modified Merge sort (henceforth referred to as “MergeSel”) that cuts to   Selection sort when the sub-arrays get small enough. I.e., instead of recursively calling Merge sort all the way down to a subarray of a single element, call Selection sort instead when the   subarrays are < ax elements. The ideal value for ax will be determined by you empirically.

You might wonder why we would use Merge sort and Selection sort, instead of Quicksort and Insertion sort. Merge and Selection sorts have the same best/average/worst case complexity (nlogn, n2  respectively). We use them so our results will be as predictable as possible and not influenced by the initial “sortedness” of our input array.

Testing

The main() function of your program will generate integer arrays containing n elements           whose values are randomly distributed between 1 and 4n. Make n suitably large so that we can see past the overhead involved and get a clear picture of the performance of each of our three sorting algorithms.

First, perform a sanity check on your Merge and Selection sort implementations. Test each using several different values of n. You might start with n = {4000, 8000, 160000, 32000}.   Beyond this, you might be waiting hours for selection sort to complete.

Once you’re satisfied that the results obtained from your Merge sort and Selection sort             implementations make sense, dramatically increase the size of n and compare MergeSort with

MergeSel sort. Some reasonable values of n to start with could be {128000, 256000, 512000, 1024000, 2048000}

When comparing Merge and MergeSel, we add the additional variable ax – the size at which MergeSel kicks to Selection sort. The values for ax are completely up to you, but I suggest     starting at ax=3, 5, 7, 9, 11, etc. Your goal is to try and improve on Merge sort as much as      possible. Have fun experimenting and follow the data!

To make testing consistent for everyone, and to ensure your time is spent on the sorting         algorithms rather than writing testing code, a file named lab1.cpp containing testing code is   provided to get you started. Your job is to implement the sorting algorithms and call them at  the appropriate place in the tester code. You may modify the tester as much as you see fit, so long as your results are produced and printed in a clean, readable format.

Results

Your program should print its results to the terminal. Format your output in a way that’s easy for me to read. When I run my own functions with the tester, the output appears as follows: