Seminario Interdipartimentale di Algoritmica  

Monday, October 17, 2005, 12:00 noon
Efficient Sorting and Adaptive Sorting with Respect to Branch Mispredictions
Gabriel Moruz, University of Aarhus

DIS - Department of Computer and System Sciences
C3 Room, second floor

Abstract:

Branch mispredictions is an important factor affecting the running time in practice. We prove lower bound tradeoffs between the number of comparisons and the number of branch mispredictions performed by sorting and adaptive sorting algorithms. We show that Multiway MergeSort achieves the tradeoff for sorting by adopting a multiway merger with a low number of branch mispredictions. For adaptive sorting, we show that the 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. We also give theoretical and experimental results that show that the running time of Quicksort is adaptive. More precisely, we prove that randomized Quicksort performs expected $O(n(1+\log (1+Inv/n)))$ element swaps, where $Inv$ denotes the number of inversions in the input sequence. This result provides a theoretical explanation for the observed behavior in practice, and gives new insights on the behavior of the Quicksort algorithm. We also give some empirical results on the adaptive behavior of Mergesort and Heapsort.