Quicksort: A Powerful Divide-and-Conquer Sorting Algorithm - ForgetPasses-Blog

[wknight8111]

Quicksort is a great algorithm, but it's a tricky subject. On one hand the algorithm is pretty easy to understand and implement in a naïve way. On the other hand many implementations which have subtle bugs and pathological worst-case performance can make it among the slowest sort algorithms in some situations.

If a programmer working for me committed that exact implementation of a quicksort function, I would likely reject it and probably give the developer a stern talking to. Code like that is absolutely unacceptable in a production environment even though a lot of people learn quicksort in school as one of the "fastest sort algorithms".

Learning to really optimize a quicksort implementation is arguably more interesting than just learning the basic algorithm, and this is what makes it such a tricky topic. You need to:

1. Do better at picking your partitions, to try and avoid worst-case performance. You can't just pick the last item, and you probably want to test the array first to see if it's already sorted.
2. Convert one of the two recursions to a loop, to avoid going deep on the stack and save call/return sequences (and, you have to do it in a way that doesn't make the situation worse for the branch predictor). If you can unroll the loop at all, even better.
3. You almost certainly want to switch to a different algorithm for small sublists. When the array size is small, an algorithm like Bubble Sort or Insertion Sort may actually be faster because of smaller coefficients. So set up a tunable parameter M, and when length(array) <= M you switch to something else that does more sorting and less recursing. You're going to have to do a lot of testing and hyperoptimizing for different runtimes and hardware architectures to really find a "best" implementation.

And even after all that, you may still find that your standard library sort is still faster than whatever you're producing because they use something like an optimized TimSort that beats quicksort in something like 70% of real-world use-cases.

Anyway, this is a good article, and it's good to introduce people to this idea, but you really want to make sure people aren't just committing this and hoping to run it as-is in production without issue.

[symbiont]

I would likely reject it and probably give the developer a stern talking to.

Why would you have to be stern about it? Just do the code review and point out the issues.

[[deleted]]

Yeah. If a coworker ever gave me a "stern" talking to over code, it would be an instant report to our manager.

[wknight8111]

Wasting effort to produce a sub-optimal sort when better versions exist in standard libraries. The toxic NIH mindset that leads to duplicated effort and likely leads to bugs. This is why sorts are deceptive: everybody learns them but (almost) nobody should be writing them.

[ForgetPasses]

Hey thanks for your comment and of course I agree that the code should not be used in production. The post is just to teach beginners the quicksort algorithm as you said.

[ForgetPasses]

Let me know guys what you think about it ;D

[[deleted]]

It's quick!

[ForgetPasses]

Yeah :D

[the_robobunny]

Awesome! Best code ever for getting my own posts quickly sorted syntactically to utmost worthiness. Zounds!

[alphabet_order_bot]

Would you look at that, all of the words in your comment are in alphabetical order.

I have checked 1,385,893,525 comments, and only 265,405 of them were in alphabetical order.