Aarhus University Seal

Tradeoffs Between Branch Mispredictions and Comparisons for Sorting Algorithms

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Department of Computer Science
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 Omega(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 Omega(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.
Original languageEnglish
Title of host publicationAlgorithms and Data Structures : 9th International Workshop, WADS 2005, Waterloo, Canada, August 15-17, 2005. Proceedings
EditorsFrank Dehne, Alejandro Lopez-Ortiz, Jörg-Rüdiger Sack
Number of pages11
PublisherSpringer
Publication year2005
Pages385-395
ISBN (print)3-540-28101-0
DOIs
Publication statusPublished - 2005
EventInternational Workshop on Algorithms and Data Structures - Waterloo, Canada
Duration: 15 Aug 200517 Aug 2005
Conference number: 9

Conference

ConferenceInternational Workshop on Algorithms and Data Structures
Nummer9
LandCanada
ByWaterloo
Periode15/08/200517/08/2005
SeriesLecture Notes in Computer Science
Volume3608
ISSN0302-9743

See relations at Aarhus University Citationformats

ID: 230307