Tradeoffs Between Branch Mispredictions and Comparisons for Sorting Algorithms

Gerth Stølting Brodal and Gabriel Moruz

In Proc. 9th International Workshop on Algorithms and Data Structures, volume 3608 of Lecture Notes in Computer Science, pages 385-395. Springer Verlag, Berlin, 2005.

Abstract

Branch mispredictions is an important factor affecting the running time in practice. In this paper we consider tradeoffs between the number of branch mispredictions and the number of comparisons for sorting algorithms in the comparison model. We prove that a sorting algorithm using O(dnlog n) comparisons performs Ω(nlogd n) branch mispredictions. We show that Multiway MergeSort achieves this tradeoff by adopting a multiway merger with a low number of branch mispredictions. For adaptive sorting algorithms we similarly obtain that an algorithm performing O(dn(1+log (1+Inv/n))) comparisons must perform Ω(nlogd (1+Inv/n)) branch mispredictions, where Inv is the number of inversions in the input. This tradeoff can be achieved by GenericSort by Estivill-Castro and Wood by adopting a multiway division protocol and a multiway merging algorithm with a low number of branch mispredictions.

Copyright notice

© Springer-Verlag Berlin Heidelberg 2005. All rights reserved.

Online version

wads05.pdf (149 Kb)

DOI

10.1007/11534273_34

Links

BIBTEX entry

@incollection{wads05,
  author = "Gerth St{\o}lting Brodal and Gabriel Moruz",
  booktitle = "Proc. 9th International Workshop on Algorithms and Data Structures",
  doi = "10.1007/11534273_34",
  isbn = "978-3-540-28101-6",
  pages = "385-395",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Tradeoffs Between Branch Mispredictions and Comparisons for Sorting Algorithms",
  volume = "3608",
  year = "2005"
}