Java 7’s Dual Pivot Quicksort

In my master’s thesis I started the analysis of dual-pivot Quicksort. Apart from Yaroslavskiy-Bentley-Bloch partitioning, the method used in the Java library, I analyze in detail also Sedgewick’s dual-pivot partitioning method, and compare both to classic single-pivot Quicksort.

A unique feature of the thesis are primitive instruction counts of low-level implementations of these Quicksort variants. I describe implementations in Java Bytecode and Knuth’s MMIX assembly language.

Relation to Other Publications

I refined the analysis of dual-pivot Quicksort with Yaroslavskiy-Bentley-Bloch partitioning without pivot sampling and including pivot sampling.

Printed Version

If you plan to read a significant portion of the thesis, you might like the print-on-demand version. The preprint is content-wise identical to the printed version and suitable for printing on A5 paper.

Even though the print is nicely done, and my experience with AV Akademikerverlag was not negative, I would like to mention that it is part of an alleged predatory publisher corporation. They publish basically everything, at low cost and in the hope that the authors themselves buy a few copies to give as present to friends and family (and yep, they succeeded with me on this…)

I find this form of predatory publisher comparatively benign: the book is overpriced, but this is transparent for you: buy it or don’t. In contrast to predatory scientific journals with (apparently) fake peer-review processes, AV Akademikerverlag did not try to suggest to me (or anyone else as far as I know) that a book in their program carries value as a scientific publication.