timsort

[Martin Buchholz]

On Tue, Jul 7, 2009 at 13:28, Christopher Hegarty -Sun Microsystems Ireland
<Christopher.Hegarty at sun.com> wrote:

> Hi Martin, Josh,
>
> Thank you both for making these changes.
>
> Once we have the Blenderev I'll file a CCC request and keep you informed of
> its status.
>
> Martin:
>  I'm signing off for tonight. I can create the Blenderrev tomorrow if you
> don't get a chance. Also, I think you need an additional 'optional' for the
> final Arrays.sort method.
>

Good catch!  I did some final fixup of the IAE specs.

It's a cruel world.  Although I am the author of BlenderRev, I can't run it
myself
because it hasn't been open-sourced (and it has a third-party closed-source
dependency).  Y'all should set up a public BlenderRev server, that would
turn
a mercurial revision into a BlenderRev.
Open-sourcing my Sun ~/bin would be nice.

webrev regenerated.

Martin


>
> -Chris.
>
> Martin Buchholz wrote:
>
>> 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/<http://cr.openjdk.java.net/%7Emartin/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 <mailto:
>> 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/7e735d9e/attachment.html>