# Tradeoffs Between Branch Mispredictions and Comparisons for Sorting Algorithms

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*(*d**n*log *n*) comparisons performs Ω(*n*log_{d}
*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*(*d**n*(1+log (1+Inv/*n*)))
comparisons must perform Ω(*n*log_{d} (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**

**BIBT**_{E}X 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"
}