Dual-pivot and beyond: The potential of multiway partitioning in quicksort

This article is an invited summary of my dissertation. It appeared in the distinguished dissertations column of it – Information Technology as has been a tradition for recipients of the GI Dissertationspreis.

A more detailed, German version of this article appears in the official proceedings of GI Dissertationspreis (alongside the contributions of all nominees).

The summary is intended to be accessible to a wider audience. It highlights the algorithmic insights from my work, in particular how simulating the effect of a multiway partitioning method by several runs of standard single-pivot partitioning can pinpoint the benefit of the former in terms of fewer memory transfers (scanned elements).

This summary extends and subsumes an earlier informal write-up of the dual-pivot Quicksort story.