How does this Java Comparator function correctly?

Question

I recently met a comparator that on the surface does not look right. However, I could not find the input for it, which leads to the fact that the comparator produces the wrong result.

It incorrectly treats values ​​as equal if o1 <= o2, and correctly returns 1 if o1> o2.

I tried to simplify the script as much as possible below. Can anybody:

• Explain why this is normal.
• Create an input array due to which it does not properly sort the result.

I experimented with him quite a bit, and I throw a towel!

package comparator; import java.util.Arrays; import java.util.Collections; import java.util.Comparator; import java.util.List; public class BadComparator implements Comparator<Integer> { public int compare(Integer o1, Integer o2) { // Generally Accepted implementation //return o1 - o2; // Incorrect(?) Implementation return (o2 < o1) ? 1 : 0; } public static void main(String[] args) { List<Integer> intList = Arrays.asList(10, 9, 8, 1, 2, 3, 7, 4, 5, 6); Collections.sort(intList, new BadComparator()); System.out.println(intList); } } 

Answer 1

Collections.sort is implemented as mergesort. looking at the source, all comparison conditions >0 or <=0 , which randomly consider the negative case as the same case. another implementation may fail.

Per jbellis comment: “It's not really“ just luck, ”though - Collections.sort is guaranteed to be“ stable, ”which means that equal items should be in the same relative order after sorting. I'm not sure if it's possible to create a stable implementation of a sort that can't handle this comparator, but I can't come up with one on my head. "

 private static void mergeSort(Object[] src, Object[] dest, int low, int high, int off, Comparator c) { int length = high - low; // Insertion sort on smallest arrays if (length < INSERTIONSORT_THRESHOLD) { for (int i=low; i<high; i++) for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--) swap(dest, j, j-1); return; } // Recursively sort halves of dest into src int destLow = low; int destHigh = high; low += off; high += off; int mid = (low + high) >> 1; mergeSort(dest, src, low, mid, -off, c); mergeSort(dest, src, mid, high, -off, c); // If list is already sorted, just copy from src to dest. This is an // optimization that results in faster sorts for nearly ordered lists. if (c.compare(src[mid-1], src[mid]) <= 0) { System.arraycopy(src, low, dest, destLow, length); return; } // Merge sorted halves (now in src) into dest for(int i = destLow, p = low, q = mid; i < destHigh; i++) { if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0) dest[i] = src[p++]; else dest[i] = src[q++]; } } 

Answer 2

This does not work for me. He concludes:

 [10, 9, 8, 1, 2, 3, 7, 4, 5, 6] 

(which matches the input order). This is not guaranteed, though ... I suspect that you may have chosen items that are either already in the correct order, or decide that they are "equal" and leave them alone.

Note that o1 - o2 also does not work ... consider if o1 = Integer.MIN_VALUE and o2 = 1 ... you could fix this by translating to long values ​​first, of course, of course.

A more natural implementation would be

 return o1.compareTo(o2); 

or

 int i1 = o1.intValue(); int i2 = o2.intValue(); return i1 < i2 ? -1 : i1 == i2 ? 0 : 1; 

Answer 3

This works by chance; The fact that it works depends on the implementation details of Collections.sort() . Since the comparator does not do what it should do according to its contract, you cannot be sure that it will continue to work with other JVM implementations or even other versions of Oracle JVM.

It makes no sense to try to find out why this is happening.

Answer 4

This is clearly the wrong implementation of Comparator . For example, Javadoc says that:

The developer must ensure that sgn (cf. (x, y)) == -sgn (cf (y, x)) for all x and y.

In this case, this is clearly incorrect, as it can return 1, but not -1. A.

I believe that the reason this doesn't cause problems when sorting is because with the standard comparator, the two items in the list are in an acceptable order if the comparison method returns -1 or 0, but they should be replaced if it returns 1. So, at least for some sorting algorithms, it should be enough to correctly indicate whether the second argument is greater than the first.