按年被提到
20182018 · 1 次2026
算法与数据结构›经典算法与数据结构·arXiv:1805.04154 · cs.DS

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

J. Ian Munro, Sebastian Wild · 2018
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2018-09-21 · 最近 2022-04-20
2不同的人
2活跃月份
2讨论串
7被引(OpenAlex)
arXiv 摘要(候选层不写导读)

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.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论lorenzhs · 2018-09

“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 issues were found well after it was already widely deployed. Recently, it was…”

Ask HN: What open source project, in your opinion, has the highest code quality?原评论 ↗
评论orlp · 2022-04

“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 and many equal elements (at least if it has buffer memory), no matter where t…”

Changing std:sort at Google’s scale and beyond原评论 ↗