java - Javaのソートアルゴリズムは何ですか

Question

OpenJDK は内部でデータ型をどのようにソートしますか?またその理由は? 具体的なアルゴリズムについて言及できれば素晴らしいことです

Answer 1

バージョン 7 以降、Oracle の Java 実装では、10 要素を超えるオブジェクト配列にはTimsortを使用し、要素数がそれ未満の配列には挿入ソートを使用しています。Arrays.sort()と の両方に同じ考慮事項が適用されますCollections.sort()。古いバージョンの Javaでは、Timsort の代わりにMerge sortが使用されていました。

言語の他の実装 (Oracle 以外) では、仕様で義務付けられていないため、別の並べ替えアルゴリズムを使用する場合があります。ドキュメントCollectionsの引用:

このクラスに含まれるポリモーフィック アルゴリズムのドキュメントには、通常、実装の簡単な説明が含まれています。このような説明は、仕様の一部ではなく、実装ノートと見なされるべきです。実装者は、仕様自体が守られている限り、他のアルゴリズムを自由に置き換える必要があります。(たとえば、ソートで使用されるアルゴリズムはマージソートである必要はありませんが、安定している必要があります。)

数値プリミティブをソートするために、JDK 7は「デュアル ピボット クイックソート」を使用します。

Answer 2

Collections.sort()変更されたマージソートを使用します。Arrays.sort()プリミティブにはクイックソートのバリエーションを使用し、ソートにはマージソートを使用しObjectます。

Java 7 については、以下の @SebastianPaaskeTørholm からのコメントをお読みください。