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