For this programming assignment, you will implement three fundamental sorting algorithms in C or C++, namely, insertion sort, merge sort, and quicksort. Then, you will test your code for correctness, performance, and memory usage errors.

1. sorting.cpp

   First, you need to implement three algorithms for sorting integers (e.g. {-3, -9, 0, 5, 1, 5}) in an ascending order (e.g., {-9, -3, 0, 1, 5, 5 }). The algorithms to implement are insertion sort, hybrid merge sort, and hybrid quicksort.

   Here is what "hybrid" means. Both merge sort and quicksort operate in a recursive fashion. They partition the input and call themselves recursively for each part. In the default implementation, merge sort and quicksort proceed with partitioning until they reach parts of size 1 (or 2, depending on your implementation). Such a small part is not partitioned further (either because it is already sorted or just because it is too small for partitioning). In our hybrid implementation, merge sort and quicksort will stop partitioning earlier, namely, when the part length becomes 6 or smaller. As soon as a part has shrunk to ≤ 6 elements, both merge sort and quicksort will use insertion sort to sort such a small part. (Sometimes, such implementation of merge sort is called tiled merge sort; read section Optimizing merge sort of the article on Merge sort on Wikipedia.)

   The idea behind the combining recursive sorting algorithm with insertion sort is as follows. On large inputs, merge sort and quicksort are faster than insertion sort (since the time complexity of the former is O(n * log(n)), while the time complexity of the latter is O(n * n), where n is the size of the input). However, insertion sort can beat both merge sort and quicksort on small inputs. What it means for the input to be small significantly depends on the machine used to run sorting code, but for this assignment, we will assume that arrays of length 6 or smaller can be more efficiently sorted using insertion sort.

   You will write your code in file sorting.cpp. This file should include definitions of your three sorting functions and, possibly, some other functions if you need them. Signatures of your sorting functions should look as follows:

   	int insertion_sort(int *items, const int n);
   	int merge_sort(int *items, const int n);
   	int quick_sort(int *items, const int n);
   

   Each of these functions accepts a pointer to an array of integers and the length of this array, and is expected to sort the array ascendingly. More generally, pointer items may refer not necessarily to the beginning of an array, and n should not necessarily be the length of the entire array. For example, if the whole array int *arr contains 5 integers, we can pass &arr[1] as the first argument and 3 as the second argument, which should result in the middle 3 array elements' being sorted.

   Each sorting function returns 0 if sorting was successful, and 1 if there were some errors (e.g., the input arguments were invalid).

   Try to make both your recursive sorting functions to do sorting in-place.

   The carcass for sorting.cpp is given. You just need to fill the three above mentioned functions. (Again, your sorting.cpp may contain other functions as well if needed.)

2. Testing

   You will test correctness, performance, and memory usage of your code.

   Testing correctness: First of all, you will need to make sure that your sorting code works correctly. For one thing, you can write your own tests to do it. For another thing, several tests are already written for you. These were written using googletest C++ testing framework. (Most commands for building tests, profiling, and running memory checks are written in Makefile. You do not need to alter this file, but reading through it may definitely give you some knowledge of how different useful development tools work. I expect you to start using these tools on your own for the subsequent programming assignments.)

   In order to use the correctness tests, you should

   • build googletest once (this may take a minute):
     

     make gtest

   • build correctness tests each time you change your code and want to re-test:

     make test

   • run correctness tests:

     ./sorting_tests

As a result, you will get some output, telling you whether tests are passed and, if not, why (read the diagnostic messages).

Testing Memory Usage: This test checks for memory leaks (i.e., memory allocated, but never released) and for proper array access (e.g., if an array arr contains 2 elements, you are not trying to access arr[10]). Both tests use Valgrind. In order to check for memory leaks, run make leaks. To check array access, run make bounds. Your final code should be free from memory usage errors.

Testing Performance: As soon as you know that your code works correctly, you need to test its performance. As with correctness tests, there are a few performance tests written using googletest. To use these tests,

• if you have not done it already, build googletest once (this may take a minute):
  

  make gtest

• build performance tests each time you change your code:

  make perftest

• run performance tests:

  ./sorting_perftests

These tests feed large inputs to your functions and measure the sorting time. If the time is reasonable, then tests pass. If your sorting functions work unexpectedly long, tests fail. Try to make your sorting code reasonably fast.

If performance tests fail (or, even if they do not), you may want to look at the profile of your code, i.e., at how much time each function executes. This may give you an idea of who are the most time-expensive functions. Later, you may focus your optimization effort on these villains. To profile your code, run make profile and then look at the newly created file gprof.out — it contains lots of performance data (if you change your code, you will need to regenerate this data by repeating make profile).

3. Submitting your work

   Turn in only one file — sorting.cpp. Do not forget to write your names in the header. As usually, log in to csil.cs.ucsb.edu and run

   	turnin pa2@cs32 sorting.cpp
   

   and follow instructions. You can submit your work multiple times. Please, respect the deadline.