O(n log n)のMergeSortだと思います。
ただし、次の出力は一致しません。
-1,0000000099000391,0000000099000427
1,0000000099000427,0000000099000346
5,0000000099000391,0000000099000346
1,0000000099000427,0000000099000345
5,0000000099000391,0000000099000345
1,0000000099000346,0000000099000345
4 つのノードのノードリストをシーケンス番号で並べ替えています。並べ替えは 6 回の比較を行っています。6 > (4 log(4)) なので困惑しています。誰かが私にこれを説明できますか？
回答ありがとうございます。トム、私の数学を訂正してくれてありがとう。
4つのノードを並べ替えたため、マージソートは取得されませんでした。ソートが挿入ソートに切り替わりました。
Javaでは、Arrays.sort（）メソッドは、データ型に応じてマージソートまたは調整されたクイックソートを使用し、実装効率のために、7つ未満の配列要素がソートされている場合は挿入ソートに切り替えます。（ウィキペディア、強調を追加）
Arrays.sortは、Collectionsクラスによって間接的に使用されます。
最近受け入れられたバグレポートは、JavaのSun実装が将来Pythonのティムソートを使用することを示しています：http：//bugs.sun.com/bugdatabase/view_bug.do ？bug_id = 6804124
（上にリンクされているティムソートのモノグラフは、読む価値があります。）
ある量のデータnを処理するアルゴリズムA（n）は、次のような2つの厳密に正の定数C_infおよびC_supが存在する場合、一部の関数fに対してO（f（n））にあります。
C_inf。f（n）<ExpectedValue（OperationCount（A（n）））<C_sup。f（n）
注意すべき2つのこと：
実際の定数Cは何でもかまいませんが、操作の相対的なコストに依存します（言語、VM、アーキテクチャ、または操作の実際の定義によって異なります）。たとえば、一部のプラットフォームでは、+と*のコストが同じですが、他のプラットフォームでは、後者の方が桁違いに遅くなります。
「inO（f（n））」と見なされる量は、処理しているデータのおそらく任意のモデルに基づいた、予想される操作数です。たとえば、データがほぼ完全にソートされている場合、マージソートアルゴリズムは、O（n。log（n））ではなく、ほとんどがO（n）になります。
Java ソート アルゴリズムについて興味があるかもしれないことをいくつか書き、 Collections.sort() のパフォーマンス測定を行いました。現在のアルゴリズムは、サブリストが特定のサイズになると挿入ソートを使用するマージソートです (このアルゴリズムは Java 7 で変更される可能性が非常に高いです)。
アルゴリズムが全体的にどのようにスケーリングするかを示すものとして、Big O 表記を使用する必要があります。特定の並べ替えでは、正確な時間はこの計算で予測される時間からずれます (私のグラフでわかるように、組み合わされた 2 つの並べ替えアルゴリズムはそれぞれ異なるパフォーマンス特性を持っているため、並べ替えの全体的な時間はもう少し複雑です）。
とは言っても、大まかな目安としては、要素数を2倍にするごとに、予想時間を2.2倍にすれば、そう遠くはありません。(しかし、いくつかの要素からなる非常に小さなリストに対してこれを行うことはあまり意味がありません。)