Java 7のArrays.sort(Object[])

Java 7のEarly Access版をダウンロードしました。昨日、Joshua Bloch氏にProject Coinへ彼が提案している言語仕様の変更はすでに実装されているのかと聞いたところ、まだプロトタイプされていないということでした。で、その話のついでに、ソートの話になり、Java 7にはTimSortが入っているということで、調べてみました。

従来、コレクションフレームワークのArraysクラスのsort(Object[])は、今まではマージソートで実装されていました。しかし、Java 7にはパッケージプライベート宣言されているTimSortクラス（TimSort.java）が追加されており、Arrays.sort(Object[])（と関連する他のsortメソッド）はデフォルトでTimSortクラスのsortメソッドを使用するように書き換えられています。

TimSort.javaクラスのソースコードに書かれているJavadocコメントは以下のようになっています。

A stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when running on partially sorted arrays, while offering performance comparable to a traditional mergesort when run on random arrays. Like all proper mergesorts, this sort is stable and runs O(n log n) time (worst case). In the worst case, this sort requires temporary storage space for n/2 object references; in the best case, it requires only a small constant amount of space.

This implementation was adapted from Tim Peters's list sort for Python, which is described in detail here:

http://svn.python.org/projects/python/trunk/Objects/listsort.txt

Tim's C code may be found here:

http://svn.python.org/projects/python/trunk/Objects/listobject.c

The underlying techniques are described in this paper (and may have even earlier origins):

"Optimistic Sorting and Information Theoretic Complexity"
Peter McIlroy
SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms),
pp 467-474, Austin, Texas, 25-27 January 1993.

Tim Peters氏の実装に基づいているので、TimSortと呼ばれているようです。

200万個のデータでベンチマークしてみました。ランダムなデータ、ソートされたデータ、逆順にソートされたデータの3種類で従来のマージソートと比較してみました。結果は、マージソートの処理時間を100とすると、ランダムなデータの場合は109.3。ソートされたデータでは44.4。逆順にソートされたデータでは27.3でした。

ランダムなデータに関しては、従来のマージソートの方が早いですが、ソートされたデータや逆順にソートされたデータの場合には、TimSortの方が圧倒的に早いようです。

ランダムなデータに関しても、（環境がないので測定していませんが）HotSpot Server VMで遜色ないスピードが出れば、ほとんどのデータでに関しては、スピードアップが図られることになると思います。また、Collections.sort(List)も内部的には、Arrays.sort(Object)を使用していますので、Java 7ではソートの高速化が行われることになります。

今回のJavaへのTimSortの移植作業は、Joshua Bloch氏が行っています。