Sorting

This is so fundamental that you’re probably wondering why I even bother to put it here. Read on…

Input

Array size, data type, algorithm, sort order

Output

Running time of different parts of the code

Program

1. Create an array of the given data type and size, and populate it with random values
2. Implement multiple sorting routines:
   1. InsertionSort
   2. MergeSort
   3. QuickSort
   4. ShellSort
   5. CountingSort
3. Implement different optimizations for these
4. Test that the final array is sorted

Run

your implementation with different array sizes. Your program should report the time to generate the array, sort it and test that it has been sorted correctly.

Write a wrapper script that captures the above running times and generates a plot that shows the comparative performance of different sorting routines: the x-axis is the array size and the y-axis is the time. You should have multiple versions of the above sorts with different implementations.

What do you expect the graph to look like? Can you explain the shape of what you actually get? 

Should you combine different sorting approaches? What would you expect, and how would you do this?

What factors impact the performance that you observe?

Report

Compile your experiments and describe your findings. What conclusions do you draw from this? What do you hypothesize, and how did you test your hypotheses?