woshidan's blog

あいとゆうきとITと、とっておきの話。

JavaのCollections.sortは何ソートなのか

最近、本の中身をがっつりそのまんま、みたいなブログに書きにくい勉強のやり方をしているので、なかなかネタがないですね。

なので、ちょっと気になったことをメモしておきます。

Javaはコレクションクラスに対して、

Collections.sort(someList, new SomeComparator());

のようにして、ソートを行うことができるのですが、このソートが何ソートなのか気になったので調べました。

Collections (Java Platform SE 6)

ソートアルゴリズムは修正マージソートです。このソートでは、下位のサブリストでの最高レベルの要素が上位のサブリストでの最低レベルの要素より小さい場合、マージは省略されます。このアルゴリズムは、常に n log(n) のパフォーマンスを提供します。 指定されたリストは変更可能でなければなりませんが、サイズ変更はできなくてもかまいません。この実装は、指定されたリストの配列へのダンプ、配列のソート、リストの繰り返し処理を行うことにより、配列の対応する位置から各要素を再設定します。これは、リンクされたリストを適所にソートしようとした場合の n2 log(n) のパフォーマンスになるのを回避します。

Collections (Java Platform SE 7)

実装にあたっての注意:この実装は安定した適応型の反復マージソートです。このソートでは、入力配列がランダムに順序付けられる場合は従来のマージソートのパフォーマンスを提供しながら、入力配列が部分的にソートされている場合は必要となる比較回数が n lg(n) よりもかなり少なくなります。入力配列がほとんどソートされている場合、この実装ではおよそ n 回の比較が必要になります。一時ストレージの要件は、ほとんどソートされている入力配列用の小さな定数から、ランダムに順序付けられた入力配列用の n/2 のオブジェクト参照までさまざまです。

この実装では、その入力配列で昇順と降順を等しく利用するため、同じ入力配列のさまざまな部分で昇順と降順を利用できます。それは 2 つ以上のソートされた配列をマージするのに最適です。つまり、それらの配列を連結し、結果となる配列をソートするだけです。

この実装は、Tim Peters 氏による Python 用のリストソート (TimSort) から応用されました。それは、『Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms』(1993 年 1 月) の 467 - 474 ページに記載されている、Peter McIlroy 氏の「Optimistic Sorting and Information Theoretic Complexity」からの技術を採用しています。

この実装は、指定されたリストの配列へのダンプ、配列のソート、リストの繰り返し処理を行うことにより、配列の対応する位置から各要素を再設定します。これは、リンクされたリストを適所にソートしようとした場合の n2 log(n) のパフォーマンスになるのを回避します。

Java 6の方の説明を見た後Java 7の方の劣化版Sortみたいなことを手動でやってみたくてどうしようかな、と思っていたのですが、 なんていうか、まあ、バージョンによって中身違うんですね!!

qiita.com

上の記事などを見てるといまAndroidJavaのバージョンはJDK 7の方でいいみたいなので、Sort書いてみたかった話は一旦忘れておきます...。