(Logo)   IMADA
University of Southern Denmark IMADA - Department of Mathematics and Computer Science
   

COMPUTER SCIENCE COLLOQUIUM

Fast Stable Sorting, Adapting to Existing Runs

Ian Munro
Cheriton School of Computer Science
University of Waterloo

Friday, 02 November, 2018 at 14:15
DIAS Conference Room

ABSTRACT

Sorting is probably the most heavily studied task in computing. It is often required that the method be stable (i.e. records with equal keys are kept in their original order). It is also highly desirable that a method take advantage of already sorted segments of the input. Timsort is a well known procedure in both Python and Oracle's Java library for just this problem. While effective in practice, it has been hard to prove that it is an O(n lg n) technique and indeed versions of the method have been incorrect for some inputs. This led us to explore other methods for the same problem and we present two stable mergesort variants, "peeksort" and "powersort", both of which exploit existing runs and find nearly-optimal merging orders with negligible overhead. We demonstrate that our methods are competitive in terms of running time with state-of-the-art implementations of stable sorting methods.

This is joint work with Sebastian Wild. It was presented at the European Symposium of Algorithms (2018)

Host: Kim Skak Larsen


SDU HOME | IMADA HOME | Previous Page
Daniel Merkle