java - Arrays.sort の実装、具体的に何をするのか

Question

JavaでArrays.sortが使用するソートアルゴリズムは何ですか? オペレーティングシステムや入力サイズなどに応じて動的に変化しますか?

Answer 1

ソースから、OpenJDK での動作を確認できます。プリミティブ型の場合、短い配列には挿入ソートを使用し、長い配列には変更されたクイックソートを使用します。オブジェクト配列の tim ソート。

Java 6 Arrays.sort()

OSがソートにどのように影響するかわかりません。

Answer 2

のドキュメントをご覧くださいArrays.sort。

実装に関する注意: この実装は、入力配列がランダムに並べ替えられている場合に従来のマージソートのパフォーマンスを提供しながら、入力配列が部分的にソートされている場合に n lg(n) よりはるかに少ない比較しか必要としない、安定した適応型の反復マージソートです。入力配列がほぼソートされている場合、実装には約 n 回の比較が必要です。一時記憶域の要件は、ほぼ並べ替えられた入力配列の小さな定数から、ランダムに並べられた入力配列の n/2 オブジェクト参照までさまざまです。

この実装では、入力配列で昇順と降順を等しく利用し、同じ入力配列のさまざまな部分で昇順と降順を利用できます。並べ替えられた 2 つ以上の配列をマージするのに適しています。単に配列を連結し、結果の配列を並べ替えるだけです。

この実装は、Tim Peters の Python 用リスト ソート (TimSort) から採用されました。離散アルゴリズムに関する第 4 回 ACM-SIAM シンポジウムの議事録、pp 467-474、1993 年 1 月の Peter McIlroy の「Optimistic Sorting and Information Theoretic Complexity」の技術を使用しています。

ソースコードを見てみましょう: Arrays.sort.

Answer 3

sortメソッドがオーバーロードされています。

Java 7 については、ここから始まるさまざまなタイプの実装ノートを 参照してください。