May 14, 2019

I have come across a classic algorithm question - quick sort on the Internet. I was surprised that the majority of the software developers did not care about performance at all and voted a solution with horrible performance. I really don't like that top-voted solution. I understand that we should always use the sorted() method in Python, but if this is an interview question, I do think it is worth my effort to revisit the performance perspective of the code.

I did some simple tests on that code. First, let's generate a random numpy array.

I am now designing my Python quicksort1() migrated from the C++ code.

Let's test it.

OK. Now let's look at the top voted solution on Stack Overflow.

What is the best performance that we can get? Let's look at the sorted() method.

You can also use the following code to verify the result is correct.

Now you have an idea of how fast your quick sort algorithm runs!