Preprint (full version):
Sam Buss and Alexander Knop
"Strategies for Stable Merge Sorting"
Submitted for publication, February 2019
Download full (preprint) version
preprint.
Abstract:
We introduce new stable, natural merge sort algorithms, called
2-merge sort and α-merge
sort. We prove upper and lower bounds for several merge
sort algorithms, including Timsort, Shiver's sort, α-stack sorts, and our
new 2-merge and α-merge sorts.
The upper and lower bounds have the forms
$c \cdot n \log m$ and $c \cdot n \log n$
for inputs of length n comprising m monotone runs. For
Timsort, we prove a lower bound of $(1.5{-}o(1)) n \log n$. For 2-merge sort,
we prove optimal upper and lower bounds of approximately
$(1.089 \pm o(1))n \log m$.
We prove similar asymptotically matching upper and lower bounds for
α-merge sort, when φ<α<2, where φ is the
golden ratio.
Our bounds are in terms of merge cost; this upper bounds
the number of comparisons
and accurately models runtime.
The merge strategies can be used for any stable merge sort, not just
natural merge sorts. The new 2-merge and α-merge sorts have better
worst-case merge cost upper bounds and are slightly simpler to implement than
the widely-used Timsort; they also perform better in experiments. We report
also experimental comparisons with algorithms developed by Munro-Wild
and Juge
subsequently to the results of the present paper.
Conference proceedings versions:
Sam Buss and Alexander Knop
"Strategies for Stable Merge Sorting"
Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019
pp. 1272-1290.
Download conference proceedings version.
SODA conference version.