Preprint:

    Sam Buss and Alexander Knop
    "Strategies for Stable Merge Sorting"
    Preprint, December 2017.

    Download 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 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. These merge strategies can be used for any stable merge sort, not just natural merge sorts.
These 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.

Back to Sam Buss's publications page.