Benchmarking Sorting Algorithms

This is the fun part—benchmarking our sorting algorithms! I saved our Mergesort code from inside a file called mergesort_1.py. The strategy we’ll follow to benchmark our code is to first generate an array of integers in random order and then benchmark how quickly Mergesort can sort the array. (The following code contains some new elements we haven’t encountered yet, but I’ll walk through them shortly.)

As usual, we begin by importing the timeit module. However, the code is divided into two sections. In addition to our test_code, we now also have setup_code. Let’s take a look at what the setup_code is all about.

To test out Mergesort, we first generate an array containing integers in random order and then perform Mergesort on that array. Technically, we could have put all of our code inside our test_code string. However, our true goal is to benchmark the Mergesort algorithm alone. Generating the random array is setting things up for Mergesort to do its work. As such, we don’t care to measure how long it takes to generate the array; it’s just setup code.

This is why timeit allows us to put our “setup code” inside a separate string, which we brilliantly named setup_code. This is excluded from the benchmark itself. That is, timeit will only measure the running time of the test_code, and not the setup_code.

As you can see, we pass the setup_code into an argument setup inside the repeat method:

However, there’s a sneaky gotcha with setup code that’ll bite you if you’re not careful.

Gotcha: Accidentally Running the Setup Code Just Once

I mentioned earlier that there are two major differences between the repeat and number. We already looked at the first difference, and now we’ll look at the second, which is hugely important.

If you pass in the arguments repeat=5, number=1, the timeit method will run both the setup code and the test code 5 times. However, if you did the opposite and passed in repeat=1, number=5, the setup code is executed only once, followed by the test_code running 5 times in a row.

This may not matter in some cases, but it can certainly matter when benchmarking sorting algorithms. That is, if the setup code is executed only once, the array is completely sorted after the first run. When the computer executes the sorting algorithm the next 4 times, we’re sorting an array that’s already completely sorted!

Mergesort takes the same amount of time whether the array is already sorted or not, but other sorting algorithms like Insertion Sort run way faster when the array is already sorted. On the flip side, as you saw in the previous chapter, Quicksort runs much slower when the array is already sorted. So, if we only run our setup code once, our benchmarking results are going to be skewed. We need to make sure that on each run, we regenerate a randomly sorted array.