“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…”
Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs
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 条,统计用全部提及“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…”