Java.util.ArrayList.sort（）ソートアルゴリズム

Question

grepcodeのsort()メソッドのソースコードをjava.util.ArrayListに探していました。彼らは小さな配列（サイズ< 7）の挿入ソートを使用し、大きな配列のソートをマージしているようです。私は、サイズが<の配列に対してのみ挿入ソートを使用するという点で、大きな違いがあるのだろうかと疑問に思っていました。実行時間の違いは現代のマシンではほとんど目立たないでしょう。

私はCormenでこれを読んでいる：マージソートはOで実行

が（N * LOGN）最悪の場合、時間と挿入ソートOで実行される（n個の* n）が最悪の場合の時、定数挿入ソートの要素は、多くのマシンで小さな問題のサイズに対して実際にはより速くすることができます。したがって、サブ問題が十分に小さくなったときにマージソート内で挿入ソートを使用することによって、再帰の葉を粗くすることは意味があります。

マージソートと比較して、私は、時間を実行しているの違いの前に（多分サイズ< 100件まで）その後、私は大きいサイズの挿入ソートを使用して検討すると、私が必要とするいくつかのコンポーネントのソートアルゴリズムを設計していた場合、明らかになる。

私の質問は、サイズ< 7に到着した後の分析は何ですか？

Answer 1

最新のマシンでは、実行時間の差はほとんど目立たないでしょう。あなたは、全体的なソートアルゴリズムが再帰的であることを認識し、そして小さな配列をソート効果的にその再帰の基本ケースであるとき、それは小さな配列をソートするためにかかる時間

が非常に重要になります。

数字7がどのように選ばれたかについての内部情報はありません。しかし、小さなアレイで競合するアルゴリズムをベンチマークし、それに基づいて最適なアルゴリズムとしきい値を選択した結果、それが行われなかったのであれば、私は非常に驚くだろう。

P.S. Java7はデフォルトでTimsortを使用することを指摘しておく価値があります。

Answer 2

http://en.wikipedia.org/wiki/Timsort

「Timsortは、実世界のデータの多くの種類にも実行するように設計されたマージソート、挿入ソート由来アルゴリズムを、ソートハイブリッドです...アルゴリズムは、既にあるデータのサブセットを見つけますサブセットを使用してデータをより効率的にソートします。これは、実行と呼ばれる特定のサブセットを、特定の基準が満たされるまで既存の実行とマージすることによって行われます。番号7について

：

は」...また、ギャロップすると、最初の要素は、他の実行の最初の7つの要素の一つではない場合にのみ、有益であることがわかる。これはまた、設定されているMIN_GALLOPになります。ギャロッピングモードの欠点を避けるために、マージ関数はmin-gallopの値を調整します。要素が現在検討中の配列（しばらく連続して要素を戻していた配列）からのものであれば、 min-gallopの値が1減少し、それ以外の場合は1増加してgallopingモードに戻るのを阻止し、ランダムなデータの場合min-gallopの値が大きくなり、ギャロッピングモードへの復帰が決して起こらないこと。

merge-hiを使用する場合（つまり、右から左にマージする場合）、ギャロッピングはデータの右端、つまり最後の要素から開始する必要があります。初めからギャロッピングしても必要な結果が得られますが、必要以上に多くの比較ができます。したがって、ギャロッピングのアルゴリズムには、ギャロッピングが開始されるべきインデックスを与える変数の使用が含まれる。したがって、アルゴリズムは、任意のインデックスでギャロッピングモードに入り、上で述べたように継続することができ、次のインデックスで1,3,7、...、（2k-1）...現在のインデックスからも同様です。 merge-hiの場合、インデックスへのオフセットは-1、-3、-7、...」となります。

Answer 3

私はこのスレッドを今後訪ねて自分自身の研究を文書化する人にこれを投稿しています。私は7を選ぶの謎に答えを見つけるために私の探求では、この優れたリンクに出くわし：

Tim Peters’s description of the algorithm

あなたは、「コンピューティングminrun」というタイトルのセクションをお読みください

要点を与えるために、。 minrunはアルゴリズムが挿入ソートを使用して開始する配列のカットオフサイズです。したがって、常にソートされた配列配列全体をソートするためにマージ操作を実行する必要があるサイズ "minrun"。

java.util.ArrayList.sort（）では、「minrun」は7に選択されていますが、上記のドキュメントを理解する限り、その神話を壊滅させ、2のべき乗256未満と以上8.文書からの引用：

256でバイナリ挿入中のデータ移動コストはソート明確に傷つけ、および8での機能の数の増加は明らかに傷つける呼び出します。ピッキングの2乗が重要ですので、マージは完全にバランスがとれます（次のセクションを参照）。

私が作っているポイントは、TimSortのパフォーマンスを損なうことなく、「minrun」が64未満の2の累乗（または2の累乗）になることです。