Here is my full list of publications.
I’m generally interested in efficient algorithms and data structures, and their mathematical analysis.
By determining the exact constant factors of their performance characteristics, I develop improvements for the fundamental building blocks of computer science like sorting, selecting and searching in dictionaries.
Timsort is a widely used adaptive sorting method that exploits existing runs in the input. A correct, efficient implementation is not trivial as witnessed by the series of bugs in the Python and Java libraries.
We found a practical drop-in replacement of Timsort’s merge rules that is provably better, can be implemented efficiently, and gives a principled solution of the underlying problem.
Java nowadays uses a dual-pivot Quicksort, the Yaroslavskiy-Bentley-Bloch (YBB) Quicksort. I did the first average-case analysis of this algorithm, and an extension of the analysis of YBB Quicksort became my dissertation project.
To see dual-pivot Quicksort in action, check out the animated visualization of the algorithm (thanks to Brad Lyon)!
Rectification of Names. Note that I referred to YBB partitioning simply as Yaroslavskiy’s algorithm in my publications finished before 2016, but besides Vladimir Yaroslavskiy, also Jon Bentley and Joshua Bloch were involved in the development of the algorithm early on, so it is more appropriate to call their algorithm YBB Quicksort.
Apart from the analysis of the new Quicksort variant, I was also able to fill some remaining gaps in the our understanding of standard Quicksort.
- We found the first precise and rigorous average-case analysis of branch mispredictions in Quicksort.
- I found a way to analyze median-of-k Quicksort on equal keys. The extension of Robert Sedgewick’s analysis was open since 1977. Even though my analysis applies only when there are many dulicates present, this is one of the results I am most proud of.
Apportionment and Stick Cutting
With a group of peers I’ve explored models for the evolution of cooperation.