How does this Java Comparator function properly?

Question

I recently came across a comparator that on the surface looks incorrect. However, I've been unable to come up with an input to it that causes the comparator to produce the wrong result.

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

I've tried to simplify the scenario as much as possible below. Can anyone either:

1. Explain why this is ok.
2. Produce an input array that causes it to sort the output incorrectly.

I've experimented with it quite a a bit and I'm throwing in the 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

It doesn't work for me. It produces the output of:

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

(which is the same as the input order). That's not guaranteed though... I suspect it happens to have picked elements which are either already in the right order, or it decides they're "equal" and leaves them alone.

Note that o1 - o2 is also broken... consider if o1 = Integer.MIN_VALUE and o2 = 1... you could fix that by converting to long values first, 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;