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.

Back to Sam Buss's publications page.