Benchmarking Sorting
For this question, you will be benchmarking some code to see how it performs, and analysing the results for statistical significance. Throughout this course, we have been doing what most people do: run the program a few times (maybe with %timeit) and looking at the averages. We now know that isn't quite enough to draw conclusions.

In the provided implementations.py, I have implemented several sorting algorithms in different ways. Each sorts NumPy arrays not-in-place (i.e. they do not modify their input array, but return a new array).

The question is simple: what can you say about which implementations are faster/slower?

Data Creation
We are concerned with the seven sorting implementations given in the all_implementations array: qs1, qs2, qs3, qs4, qs5, merge1, partition_sort. As you might guess, there are several QuickSort implementations, one Merge Sort, and one QuickSort-like thing I have named “partition sort”.

Write a program create_data.py that generates random arrays, and uses time.time to measure the wall-clock time each function takes to sort them. You may write loops in the create_data.py program.

We are concerned about (1) arrays with random integers, which are randomly sorted, (2) arrays that are as large as possible, and (3) being able to meaningfully analyse the results. [Note: see the restrictions below.]

You're going to want enough data points that you can assume normality for your analysis. It's likely that your results will be somewhat-normally-distributed, but not precisely. You'll need a large enough 
 to proceed with tests that assume normality anyway.

You can import implementations.py and iterate through the relevant sorting functions like this:

import time
from implementations import all_implementations
# ...
for sort in all_implementations:
    st = time.time()
    res = sort(random_array)
    en = time.time()
In this program, create a DataFrame in a format that makes sense, and save it as data.csv, something like this:

data.to_csv('data.csv', index=False)
Restriction #1: processor time
Your create_data.py must run in at most 60 seconds on a CSIL workstation (single-threaded). You should be able to SSH to one of them and run your code there; the modules you need should be installed.

You can check the running time, or enforce a time limit (respectively) with commands like these:

time python3 create_data.py # just check the time
timeout -s SIGKILL 60 python3 create_data.py # kill after 60 seconds
This restriction is imposed to limit the number of samples you can collect. This is generally realistic: I have sized this question so you don't have to wait too long to get data, but often the code you're benchmarking will take so long that it's prohibitive to collect thousands of data points. My intention is to give you a realistic data-collection limit, without making you wait overnight for “good” results.

You may also experience a certain amount of noise in your samples due to noisy neighbours. It's probably unlikely if you choose a random workstation, but more likely on one of the CPU servers.

Restriction #2: run count
When creating your data, you must run each sorting implementation an equal number of times.

In this artificial situation, you could run the test a few times, decide which sorting functions are more or less critical to have data for, and bias your experiment to collect more of the nearly-equal values. That's not realistic in general, where it might not be feasible to run the experiment a dozen times. (Technically, something like this could be done as a pilot study, but I'm going to call it “cheating by knowing the answer before your experiment”.)

Data Analysis
Once you have some data, you'll need to do some analysis to decide which sorting implementations are faster/slower/indistinguishable. You will need a statistical test that can be used to determine if the means of multiple samples are different, and then decide which ones. Hmm…

In your analysis, you can almost certainly apply the lesson from the “It's Probably Okay” section in lecture: if you have more than about 40 data points and they are reasonably-normal-looking, then you can use a parametric test.

Create a program analyse_data.py that reads the data.csv that you produced above and does the relevant statistical analysis. It should print the information you used to answer question 3 below, but there is no specific format required.

Aside: Why Aren’t More Users More Happy With Our VMs?, a research talk about how hard benchmarking code can be, and how tricky the analysis can be (which contains nothing that will help you do this exercise, but it's interesting anyway).