CS 269S, Fall 2017: Theory Seminar
Bren Hall, Room 1300, 1pm

December 8, 2017:

Quadratic Time Algorithms Appear to Be Optimal for Sorting Evolving Data

Speaker: Juan Jose Besa Vial

Abstract. We empirically study sorting in the evolving data model. In this model, a sorting algorithm maintains an approximation to the sorted order of a list of data items while simultaneously, with each comparison made by the algorithm, an adversary randomly swaps the order of adjacent items in the true sorted order. Previous work studies only two versions of quicksort, and has a gap between the lower bound of Ω(n)Ω(n) and the best upper bound of O(nloglogn)O(nlog⁡log⁡n). The experiments we perform in this paper provide empirical evidence that some quadratic-time algorithms such as insertion sort and bubble sort are asymptotically optimal for any constant rate of random swaps. In fact, these algorithms perform as well as or better than algorithms such as quicksort that are more efficient in the traditional algorithm analysis model.

William Devanny, Juan Jose Besa Vial, David Eppstein, Michael Goodrich, and Timothy Johnson, University of California, Irvine, USA