Alejandro López-Ortiz, University of Waterloo, will have a seminar titled Multi-Pivot Quicksort: Theory and Experiments. The seminar will take place on Wednesday, 19 Marcch 2014 at 13:15 in P3.
Abstract
Recently Vladimir Yaroslavskiy proposed a dual pivot quicksort algorithm that, contrary to prior theory and intuition, outperforms standard quicksort by a a significant margin under the Java JVM. More recently, this algorithm has been analysed in terms of comparisons and swaps by Wild and Nebel but fail to resolve the disagreement between theory and practice. We provide strong theoretical and practical evidence that cache behavior is causing most of the performance differences in these algorithms.
Lastly, we propose 3-pivot variant showing a 7-8% performance improvement over the previously best known quicksort algorithms.
Welcome!
