| Branch mispredictions don’t affect mergesort | |
| Authors: | Amr Elmasry, Jyrki Katajainen, and Max Stenmark |
| Published in: | Proceedings of the 11th International Symposium on Experimental Algorithms, Lecture Notes in Computer Science 7276, Springer-Verlag (2012), 160-171 |
| Full text: |  PDF (163 kB) |
| DOI: | 10.1007/978-3-642-30850-5_15 |
| Copyright: | © Springer-Verlag |
| Abstract: | In quicksort, due to branch mispredictions, a skewed pivot-selection strategy can lead to a better performance than the exact-median pivot-selection strategy, even if the exact median is given for free. In this paper we investigate the effect of branch mispredictions on the behaviour of mergesort. By decoupling element comparisons from branches, we can avoid most negative effects caused by branch mispredictions. When sorting a sequence of n elements, our fastest version of mergesort performs n log2 n + O(n) element comparisons and induces at most O(n) branch mispredictions. We also describe an in-situ version of mergesort that provides the same bounds, but uses only O(log2 n) words of extra memory. In our test computers, when sorting integer data, mergesort was the fastest sorting method, then came quicksort, and in-situ mergesort was the slowest of the three. We did a similar kind of decoupling for quicksort, but the transformation made it slower. |
| Related: |  HTML (Slides) HTML (Slides) HTML (Source code) HTML (Errata) |
| BibLATEX: | @inproceedings{EKS2012C,
author = {Amr Elmasry and Jyrki Katajainen and Max Stenmark},
title = {Branch mispredictions don't affect mergesort},
booktitle = {Proceedings of the 11th International Symposium on Experimental
Algorithms},
series = {Lecture Notes in Computer Science},
volume = {7276},
publisher = {Springer-Verlag},
year = {2012},
pages = {160--171},
}
|