Multi-pivot Quicksort aka 3-pivot Quicksort

“Object-oriented programming is an exceptionally bad idea which could only have originated in California.” –Edsger W. Dijkstra

The quote is by an extremely well known programmer who happened to teach for many years at the University of Texas.  In Texas, he faced other worrisome problems, perhaps related to objected oriented programming, where he was extremely concerned that the university was considering teaching Java instead of Haskell to introductory programming students.  His strongly worded letter where he describes “how I can survive in a place like Austin, Texas” offers thought provoking reading for any programmer.

I am starting the discussion of quicksort with this relevant digression for multiple reasons – some of the most elegant computer science algorithms used prominently today were developed in the 50s & early 60s (AVL trees, quicksort, Dijkstra’s shortest path) and some of the secrets to the elegance of these algorithms lies in the original papers.  In the case of AVL trees – skewed hand drawn binary trees. Similarly, Dijkstra’s most famous algorithms was drawn with pencil and paper while he and his fiancee rested at a coffee shop for 20 minutes and he stated that the pencil and paper approach was a key aspect to the elegance of the algorithm.  So it is almost with some sadness that I’m writing a 3-pivot quicksort algorithm today in Java but the dual-pivot quicksort version became famous in Java and much work went into optimizing it. Therefore, comparing 3-pivot quicksort against Java’s highly tuned dual-pivot quicksort makes sense. Also, another side note – Dijkstra’s 3-way partitioning algorithm for quicksort may ruin your searches for 3-pivot quicksort algorithms, perhaps for that reason, the paper with the best 3-pivot quicksort I know of is called, “Multi–Pivot Quicksort: Theory and Experiments” .

Surprisingly, as of November 2017 I found no publicly available implementations so I wrote one and placed it on my GitHub as is the style these days when one enjoys working for free.

And how long do you think it takes to sort 10 million pseudo-random integers on my 2013 computer? 1 second with the slightly optimized multi-pivot quicksort algorithm from the paper and 10-15% slower (a little more than 1/10th of a second) with Arrays.sort() from JDK 1.8.  I think more Java developers would have noticed and implemented it already but they were too busy trying to shoehorn functional programming into the language as more and more people are realizing Dijkstra was right.

 

Part II.  How Outdated is Your Sorting Algorithm?

• Javascript: Single pivot quicksort implemented in 2008, ~10 years outdated.
• Go: Implemented in 2009 when the language was created, not yet 10 years outdated
• C++: Most sorting work was done in the late 90s and 2000s >10 years outdated.  Interestingly it seems recursion depth was a concern so 3-pivot would would have offered another option to address the issue if it was known back then.
• So most languages would see 10-20+% improvement in performance if they were updated. Add how outdated your language of choice is in the comments, thanks for reading.