quick sortよりも高速でmerge sortのように安定しているソートアルゴリズムtim sort [勘違い] - Islands in the byte stream

<追記>ベンチマークプログラムに誤りがありました。ソート済のシーケンスに対してソートを掛けていました。ご指摘ありがとうございます＞ak氏 そんな夢のようなソートアルゴリズムがあるのかというと、あるらしいんです。それがtim sortと呼ばれるアルゴリズムです。 画期的（？）なソートアルゴリズム「Sleep Sort」：濃縮還元オレンジニュース｜gihyo.jp … 技術評論社 このあたりで拾ってきたネタですね。 merge sortを改良したアルゴリズムで、安定*1しており、しかも実行速度にも優れているとか。アルゴリズムの性能の評価は済んでいるらしく、CPythonやJDK7には既に導入済みのようですね。 ならば当然Perlのソートも…と考えるわけですが、まず評価のためにJavaのソースをC++にそのまま移植してみました。それがこれ（いちおうテスト済）： https://github.co

[gfx]

blogged

[thimura]

既に指摘されてる通り、二回目以降はソート済みデータをソートしているだけになっていた。tim sort は部分的にソート済みのデータであれば速いが、ランダムなデータであれば他と同等か、余分な処理をしている分遅くなる

[valinst]

なるほど、と思ったけど追記で特に高速ではないとな

[ether70]

quick sortよりも高速でmerge sortのように安定しているソートアルゴリズムtim sort [勘違い] - Islands in the byte stream

[edvakf]

英語ウィキペで「ほとんどの場合ソートしたい配列は既に大部分ソート済みなため速い」とか書いてあるので、結果的にそれがわかった勘違いだったのかも。

[UDONCHAN]

がーん

[takoashi_net]

よく読んでない。すごいんだよね。

[eiji8pou]

で、実際どんなアルゴリズムなのか誰か日本語訳してー。

[ideo]

画期的なソートアルゴリズム

[isano]

へ～

[Watson]

興味深い

[jontamasan]

こんど使ってみゆ

[sakuragari_nobu]

そろそろ応用情報技術者試験の勉強を始めるか…

[hiro_256]

これはメモ。

[coinlocker]

tim sort

[seaview_p35]

“Perlに移植する価値がありそうです“ですと…

[miyagi12]

あとで

[sheile]

SleepSortの記事は読んだのに、リンクされているTimSortは読んでいなかったや。

[Akaza]

追記有

[karupanerura]

Sort::Timの予感！

[terurou]

なにこれ気になる。Java7でも実装されてるらしい

[tanakh]

まじで!?

[naohaq]

むむっ。

[Crimson_Apple]

どこかで見たことある文字だとおもったらJDK7か。あとでソースみてみよっと。

[mohno]

「アルゴリズムの性能の評価は済んでいるらしく、CPythonやJDK7には既に導入済み」←へぇぇ。メモリ使用量とか、色々検証が知りたいところ。

[Ehren]

「アルゴリズムの性能の評価は済んでいるらしく、CPythonやJDK7には既に導入済みのようですね。」

[mongrelP]

ほうほう。あとで実装してみるか。

[tak158]

quick sortの名前返上だな。