HackerPapers

arXiv:1805.04154cs.DS

Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs

J. Ian Munro, Sebastian Wild

Abstract

We present two stable mergesort variants, "peeksort" and "powersort", that exploit existing runs and find nearly-optimal merging orders with practically negligible overhead. Previous methods either require substantial effort for determining the merging order (Takaoka 2009; Barbay & Navarro 2013) or do not have a constant-factor optimal worst-case guarantee (Peters 2001; Auger, Nicaud & Pivoteau 2015; Buss & Knop 2018). We demonstrate that our methods are competitive in terms of running time with state-of-the-art implementations of stable sorting methods.

arXiv comments
Journal reference
DOI
doi:10.4230/lipics.esa.2018.63
Subjects
cs.DSData Structures and Algorithms

On Hacker News

Linked by 2 identifiable commenters in 2 comments across 2 threads, from Sep 2018 to Apr 2022.

Comments linking this paper, per year.

Discussed in comments2 threads

  1. Changing std:sort at Google’s scale and beyond 1 comment

    • I have stolen a lot of ideas from scandum and extended his ideas in new ways. He is definitely a mad genius. Glidesort (on my M1 machine at least) matches fluxsort within a couple % for random data, but glidesort is robust in that it will always take advantage of pre-sorted runs…

      orlpView on HNParent context

  2. Ask HN: What open source project, in your opinion, has the highest code quality? 1 comment

    • I'm sorry, but Timsort is a bit of a hack. It's a "this seems to work well" algorithm, and it shows. It took 13 years until its claimed running time was finally proven in 2015. The four (originally three) rules for merging sequences from the stack are rather arbitrary. Multiple…

      lorenzhsView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.