On Tue, Jul 7, 2009 at 13:28, Christopher Hegarty -Sun Microsystems Ireland
<christopher.hega...@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 <j...@google.com <mailto:
>> j...@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
>>
>>
>>
