Details
-
Bug
-
Resolution: Unresolved
-
P4
-
7
Description
Debugging Sorting Errors
A legacy sorting algorithm used by java.util.Arrays.sort and (indirectly) by java.util.Collections.sort was replaced with an enhanced version called Timsort in JDK 7. The Timsort algorithm [1] is a stable, adaptive, iterative mergesort that requires far fewer than n log(n) comparisons when running on partially sorted arrays, while offering performance comparable to a traditional mergesort when run on random arrays.
The new sort implementation may throw an IllegalArgumentException if it detects a Comparable that violates the Comparable contract. The previous implementation silently ignored such a situation. The most common violations are of the Comparator rules :
* A <= B implies B >= A
* A <= B and B <= C implies A <= C
An incorrect Comparator may violate either of these conditions. Problems arise when the sort algorithm notices the result of a comparison is inconsistent with a previous comparison. The first happens most often when the items to be sorted contain duplicates and the results of separate comparisons do not agree. The second is also a case of separate comparisons not being in agreement. If you are having problems with Collections.sort() or Arrays.sort() throwing IllegalArgumentException("Comparison method violates its general contract!") run exerciseComparator() method from the demo code [link to Comparator.java] immediately before your sort() call. An AssertionError will be thrown for comparisons which your Comparator is handling incorrectly.
If the previous behavior (pre JDK 7) is desired, you should run your JVM with the new system property flag enabled. Set java.util.Arrays.useLegacyMergeSort to true. More information on this can be found in the bug report [2] or in the JDK 7 compatibility notes [3].
[1] http://en.wikipedia.org/wiki/Timsort
[2] https://bugs.openjdk.java.net/browse/JDK-6804124
[3] http://www.oracle.com/technetwork/java/javase/compatibility-417013.html
A legacy sorting algorithm used by java.util.Arrays.sort and (indirectly) by java.util.Collections.sort was replaced with an enhanced version called Timsort in JDK 7. The Timsort algorithm [1] is a stable, adaptive, iterative mergesort that requires far fewer than n log(n) comparisons when running on partially sorted arrays, while offering performance comparable to a traditional mergesort when run on random arrays.
The new sort implementation may throw an IllegalArgumentException if it detects a Comparable that violates the Comparable contract. The previous implementation silently ignored such a situation. The most common violations are of the Comparator rules :
* A <= B implies B >= A
* A <= B and B <= C implies A <= C
An incorrect Comparator may violate either of these conditions. Problems arise when the sort algorithm notices the result of a comparison is inconsistent with a previous comparison. The first happens most often when the items to be sorted contain duplicates and the results of separate comparisons do not agree. The second is also a case of separate comparisons not being in agreement. If you are having problems with Collections.sort() or Arrays.sort() throwing IllegalArgumentException("Comparison method violates its general contract!") run exerciseComparator() method from the demo code [link to Comparator.java] immediately before your sort() call. An AssertionError will be thrown for comparisons which your Comparator is handling incorrectly.
If the previous behavior (pre JDK 7) is desired, you should run your JVM with the new system property flag enabled. Set java.util.Arrays.useLegacyMergeSort to true. More information on this can be found in the bug report [2] or in the JDK 7 compatibility notes [3].
[1] http://en.wikipedia.org/wiki/Timsort
[2] https://bugs.openjdk.java.net/browse/JDK-6804124
[3] http://www.oracle.com/technetwork/java/javase/compatibility-417013.html