Message11245

I have carried on investigating this is a similar direction, and can confirm the issue is with Java's TimSort which is now the default sorting algorithm for objects. I now also have a pure java example of this issue attached (sorry its a bit messy, very quickly written). @Jeff your exactly right to see the list become "corrupted" you need the comparator to throw an exception while TimSort is doing a merge an example stack is:

	at test.TestSortJava$ComplainsComparator.compare(TestSortJava.java:30)
	at test.TestSortJava$ComplainsComparator.compare(TestSortJava.java:1)
	at java.util.TimSort.mergeLo(TimSort.java:717)
	at java.util.TimSort.mergeAt(TimSort.java:514)
	at java.util.TimSort.mergeCollapse(TimSort.java:441)
	at java.util.TimSort.sort(TimSort.java:245)
	at java.util.Arrays.sort(Arrays.java:1512)
	at java.util.ArrayList.sort(ArrayList.java:1454)
	at java.util.Collections.sort(Collections.java:175)
	at test.TestSortJava.main(TestSortJava.java:57)

I'm not clear on what the best fix is, the simplest option is to disable TimSort, which you can do by reverting to the legacy sort algorithm by setting the property -Djava.util.Arrays.useLegacyMergeSort=true see also http://stackoverflow.com/questions/13575224/comparison-method-violates-its-general-contract-timsort-and-gridlayout
I'm not sure this is a workable fix for jython as you can't ensure this property will be set when embedded in other applications but its an option?

It might also be possible to cache and restore the list somehow if we know the sort has gone wrong, I could probably write a patch for that? This will slow down sorting as we will need to compare the items in the before and after lists to determine is we are seeing this issue but I think it would be robust? For large lists this could be bad.

There are also some bugs in Java around this e.g. http://bugs.java.com/bugdatabase/view_bug.do?bug_id=7075600 (and linked) so maybe it's fixed in 9, and we should but ignore it till then? I'm not clear this is actually a Java bug though the behaviour of this case seems undefined.