Fast Stable Sorting Adapting to Existing Runs -FR

Event Details:

Please join the Faculty of Computer Science as it hosts Ian Munro, University of Waterloo, presenting, Fast Stable Sorting, Adapting to Existing Runs, as part of the seminar series.

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 both 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).

A detailed abstract can be found at http://cs.unb.ca/seminarseries/

Building: Head Hall

Room Number: 224