Strategies for stable merge sorting

DOI10.1137/1.9781611975482.78zbMATH Open1431.68021arXiv1801.04641OpenAlexW2783319652MaRDI QIDQ5236262FDOQ5236262

Authors: Alexander Knop, Samuel R. Buss 

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: We introduce new stable natural merge sort algorithms, called $2$-merge sort and $alpha$-merge sort. We prove upper and lower bounds for several merge sort algorithms, including Timsort, Shivers' sort, $alpha$-stack sorts, and our new $2$-merge and $alpha$-merge sorts. The upper and lower bounds have the forms $ccdotnlogm$ and $ccdotnlogn$ for inputs of length~$n$ comprising $m$~monotone runs. For Timsort, we prove a lower bound of $(1.5-o(1))nlogn$. For $2$-merge sort, we prove optimal upper and lower bounds of approximately $(1.089pmo(1))nlogm$. We prove similar asymptotically matching upper and lower bounds for $alpha$-merge sort, when $varphi<alpha<2$, where $varphi$ 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 $alpha$-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 Jug'e subsequently to the results of the present paper.

Full work available at URL: https://arxiv.org/abs/1801.04641

Recommendations

• SOFSEM 2006: Theory and Practice of Computer Science
• Asymptotically efficient in-place merging
• Optimizing stable in-place merging.
• Algorithms – ESA 2004
• A Simple Algorithm for Stable Minimum Storage Merging

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10)

Cited In (9)

• Galloping in fast-growth natural merge sorts
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• Stable unmerging in linear time and constant space
• On the worst-case complexity of TimSort
• A probabilistic model revealing shortcomings in Lua's hybrid tables
• Title not available (Why is that?)
• Title not available (Why is that?)
• Multiway powersort
• Title not available (Why is that?)

This page was built for publication: Strategies for stable merge sorting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236262)