timsort

[Martin Buchholz]

Josh,  thanks for the implementation notes.

I modified them by
- Peters's => Peters'
- added a space after a comma
- added a <p>
- refilled to fit into 80 cols.

I also did a bit of modernization of the javadoc for
the 6 related public sort methods.

I addressed the issue of insufficient clarity
for the optionality of IAE by using "(optional)"

+     * @throws IllegalArgumentException (optional) if the implementation
+     *         detects that the natural ordering of the list elements is
+     *         found to violate the {@link Comparable} contract


http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/

Chris, time to generate a blenderrev.
You should have one for CCC anyways.
I'll include it with my webrev.
The ball is in your court.

Martin


On Tue, Jul 7, 2009 at 12:02, Joshua Bloch <jjb at google.com> wrote:

> 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/46047bdb/attachment.html>