2015/11/03 by Sebastian Wild, Wild, Sebastian
Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Numerical Methods and Algorithms #Parallel Computing and Optimization Techniques #cs.DS
paper · pdf · doi:10.48550/arxiv.1511.01138
extended abstract for Theorietage 2015 (https://www.uni-trier.de/index.php?id=55089) (v2 fixes a small bug in the pseudocode)
openalex publication_date 2015/11/03 · arxiv created 2016/09/28 · arxiv updated 2016/09/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
I discuss the new dual-pivot Quicksort that is nowadays used to sort arrays of primitive types in Java. I sketch theoretical analyses of this algorithm that offer a possible, and in my opinion plausible, explanation why (a) dual-pivot Quicksort is faster than the previously used (classic) Quicksort and (b) why this improvement was not already found much earlier.