timsort

[Christopher Hegarty -Sun Microsystems Ireland]

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.

-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/
> 
> 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
> 
>