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