Speaker: Gabriel Moruz
Title: On the Adaptiveness of Quicksort

Abstract: In 1961 Hoare introduced Quicksort as a simple randomized sorting algorithm. Hoare proved that the expected number of comparisons performed by the algorithm is O(n log n). In practice the running time of the algorithm is strongly dependent on the number of element swaps performed, affecting it by up to a factor of two. In this paper it is proved that Quicksort performs expected O(n (1 + log(1 + Inv /n))) element swaps, where Inv denotes the number of inversions in the input sequence. Experimental results are presented supporting the influence of the number of inversions on the running time.

Joint work with Gerth Stølting Brodal and Rolf Fagerberg.

Back to the Summer School Website: [html]