timsort

Alan Bateman Alan.Bateman at Sun.COM
Tue Jun 30 10:04:56 UTC 2009


Martin Buchholz wrote:
> Hi sort team!
>
> Google would like to contribute a new implementation for sorting of 
> Object arrays,
> which has much better performance for input that is already partially 
> sorted,
> based on Tim Peter's sort used in Python.
>
> This sort is already being used in the java.util. that comes with Android.
>
> Written by Josh Bloch.
>
> http://cr.openjdk.java.net/~martin/timsort/ 
> <http://cr.openjdk.java.net/%7Emartin/timsort/>
>
> Strictly speaking, no further review may be necessary,
> since it has already seen much review by Google engineers,
> (including some who are OpenJDK committers),
> and it has seen real-world usage.
>
> Nevertheless, interested parties are invited to further review it.
>
> The proposed webrev includes some very minor change to
> the javadoc for Arrays.sort, that we would like to include,
> but are also content leaving out, or to have a Sun engineer
> shepherd through CCC (perhaps Chris or Alan?).
The results look very good.

I assume the only contentious issue is going to be the IAE when a broken 
implementation of Comparable is detected. When you say "also content 
leaving out", do you mean just the spec update, or do you mean that the 
exception won't be thrown if detected? I wonder if this will need a 
compatibility switch so as not to change the failure mode of existing 
(broken) applications.  Also, I assume failure atomicity is not possible 
here (right?); just wondering if this needs to be stated in the javadoc 
for this exception.

I haven't studied the code but from a brief glance, I think the 
"Classpath" exception might be missing from the new files in 
src/share/classes/java/util. Also, should the mergeSort implementation 
be removed or moved out of Arrays?

-Alan.




More information about the core-libs-dev mailing list