Counting Sorting Algorithm

We were recently given a problem in class that I had no idea how to start on. If anybody could give me some guidance on how to start that would be great!

The goal of the exercise is to experiment with the performance degradation caused by high rate of cache misses. To this end, you are required to implement a well-known algorithm for sorting integer numbers and try it on larger and larger input data sets.

This algorithm is the **counting sort algorithm.** At its wikipedia page, you will find a detailed description of this algorithm.

- 1. Realize a C Program implementing the counting sort algorithm. The input of this program is simply two positive integers n and k. The integer n is the size of the array to be sorted. The entries of this array are random non-negative integers less or equal than k. There will be no output for this program, since we are only interested in its running time.
- 2. Set k to be the largest value of a C int. Measure the running time for n = i * 100000000 where i is successively 1,2,3,4,5,6.
- 3. Theoretically, the number of operations performed by the counting sort algorithm is (asymptotically) proportional to n + k. Do the experimental results of the previous question reflect that fact? If not, explain why. Hint: Try to estimate the number of caches incured by the algorithm when both n and k are larger than the size of the L1 cache.