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.