コレクション。その後のソートでソートできますか？

Question

私はカスタムコンパレータクラスでCollections.sortを使用しています。私はこれがO(N log N)ランタイムの複雑さがあると聞いてきました。コレクションが変更されていない場合、後続のソートで何が起きるのか不思議です。

例として、私はsizeフィールド（私のコンパレータが並べ替える）を持つEggのArrayListを持っているとしましょう。配列リストに10個の卵を入れて並べ替えると、O(N log N)の時間がかかります。

要素を追加、削除、または変更しないでもう一度ソートすると、それでも時間はN log Nになりますか？

Answer 1

私は現在のsun javaライブラリのコードを分析していません。ただし、javadocには、マージソートが使用されていると記載されています。ほとんどのマージソートでは、既にソートされたコレクションでO（n）のパフォーマンスが得られます。これはドキュメントに記載されていませんが。私の個人的な経験から、ソートされたリストやほぼソートされたリストでは本当に良いパフォーマンスが得られました。

Answer 2

JavaDocごとCollections.sortは、マージソートアルゴリズムを使用します。

あなたはここに、あなた自身のために、それがないかを確認することができます - >http://www.sorting-algorithms.com/

Answer 3

Javadocは「低サブリストにおける最高レベルの要素が高いサブリストにおける最低の要素より小さい場合、マージは省略されている」と言います。それは何も起こらないように見えるので、速くすべきです。

いつでもテストできます。

Answer 4

マージパスがスキップされたことがドキュメントに示されている場合は、LG Nのサブプログラムにリストが分割されるため、ランタイムはLG Nになります。リニアスキャンに対する乗算は、効率の向上です。