Visualizing speed in sorting algorithms
2 min read

Visualizing speed in sorting algorithms

Introduction

My goal in this article is to show how much time complexity matters.
Understanding complexity is important to optimize our algorithms in terms of time and space. In the rest of this article, I'll assume you're familiar with the notion of complexity (and if you're not, check out this article before continuing).

Complexity is what differentiates a "fast" algorithm from a "slow" one. The difference shines even more the more items to sort there are. Most sorting algorithms have O(Nlog(N)) or O(N2) complexity. When talking about the complexity of sorting algorithms, there are three cases we take into account: the average performance, the worst case performance (think about an array sorted from highest to lowest and you'd need to sort it from lowest to highest), and the best case performance (this is the least amount of operation theoretically possible). I'll focus on the average performance, so I'll just shuffle randomly my arrays to be sorted and have multiple measures to average it out.

I won't comment on the I code used, but if you want to check it out, you can download it below:

Our sorting algorithms used

The studied algorithms in this article will be:

  • insertion sort O(N2) average performance
  • bubble sort O(N2) average performance
  • merge sort O(Nlog(N)) average performance
  • quick sort O(Nlog(N)) average performance
  • timsort O(Nlog(N)) average performance

Please note: I implemented all the sorting algorithms myself in python, except for the timsort algorithm, which is the sorting algorithm used by the sorted() function native to python.

So, what about the difference in speed of the algorithms? Well here you go:

And here is the result: all the algorithms which have an O(Nlog(N)) complexity have a runtime almost equal to zero while the two other sorting algorithms with an O(N2) complexity have several seconds of runtime, which is absolutely not negligible.

Let's now focus on our fastest O(Nlog(N)) sorting algorithms, let's add some items to our list for those algorithms to reach a couple of seconds of runtime as well:

Even amongst the fastest algorithms, there are some fastest than others. If we look at the timsort algorithm, it's clear that he's the fastest one by far, this is not only because he's inherently fast but also because the timsort (python sorted() function) is written in C which is way faster than python.

In conclusion, if you want fast code write it in C!

Thanks for reading this very short article and please consider subscribing to my newsletter, it's free and keeps me motivated!