timsort

[Joshua Bloch]

Chris,



>>
>> 1) Should we update the Arrays class description and appropriate sort
>>   methods to now refer to timsort instead of saying: "The sorting
>>   algorithm is a modified mergesort...". I know this is not strictly
>>   necessary, but you must have considered it already, right?
>
>
> No.  I totally missed it.  Good catch!
>
>

I propose this prose:

     * Implementation note: This implementation is a stable, adaptive,
iterative
     * mergesort that requires far fewer than n lg(n) comparisons when the
input
     * array is partially sorted, while offering the performance of a
traditional
     * mergesort when the input array is randomly ordered.  If the input
array is
     * nearly sorted, the implementation requires approximately n
comparisons.
     * Temporary storage requirements vary from a small constant for nearly
sorted
     * input arrays to n/2 object references for randomly ordered input
arrays.
     *
     * <p>The implementation takes equal advantage of ascending and
descending order
     * in its input array, and can take advantage of ascending and
descending order
     * in different parts of the the same input array.  It is well-suited to
     * merging two or more sorted arrays: simply concatenate the arrays and
sort
     * the resulting array.
     *
     * <p>The implementation was adapted from Tim Peters's list sort for
Python
     * (<a href="
http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
     * TimSort</a>).  It uses techiques from Peter McIlroy's "Optimistic
Sorting
     * and Information Theoretic Complexity",in Proceedings of the Fourth
Annual
     * ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, January 1993.

There are six methods that could use this prose, four in java.uti.Arrays,
and two in java.util.Collections.  Alternatively, the prose could be
included in one place, and linked to repeatedly.

            Josh
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20090707/f565409d/attachment.html>