The most comprehensive analysis of Java's dual-pivot quicksort

What is it about?

This article gives a detailed average-case analysis of dual-pivot Quicksort (YBB Quicksort). It includes pivot sampling, i.e., choosing pivots from a sample, and several different cost measures. see also https://www.wild-inter.net/publications/nebel-wild-martinez-2016

Featured Image

Why is it important?

This paper introduces that cost measure "scanned elements" which approximate the amount of data transfered from main memory and is thus related to cache misses, but unlike the latter can be analyzed precisely (because it does not depend on specific hardware parameters).