(original) (raw)

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.
�� \*
�� \*

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.
�� \*
�� \*

The implementation was adapted from Tim Peters's list sort for Python
�� \* (http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
�� \* TimSort).� 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