Internals of Collections.sort in java

Question

I am trying to understand when does elements in a list swap during sorting process . So far my understanding is during comparison when we return -1 or 0 no swapping happens and when we return 1 swapping happens. Here is the code

public class ArraySort {
    public static void main(String[] args) {
        Integer [] input = {1,10};
        List<Integer> inputList =Arrays.asList(input);
        Collections.sort(inputList,(a,b)->a>b?-1:1);
        System.out.println(inputList);
    }
}

Returns [10,1] ---- I understand this. Since we are returning 1 from comparison swapping happens.

public class ArraySort {
    public static void main(String[] args) {
        Integer [] input = {1,10};
        List<Integer> inputList =Arrays.asList(input);
        Collections.sort(inputList,(a,b)->a>b?1:-1);//changed the signs
        System.out.println(inputList);
    }
}

Returns [1,10] -- I understand this as no swapping happens since returning -1.

public class ArraySort {
    public static void main(String[] args) {
        Integer [] input = {1,10};
        List<Integer> inputList =Arrays.asList(input);
        Collections.sort(inputList,(a,b)->a>b?-1:-1); // both are negative.
        System.out.println(inputList);
    }
}

Returns [10,1] -- I DON'T understand this as why swapping happens since returning -1 should not cause swapping right? Please clarify my misunderstanding.

Again i tried posts on this forum but could get a satisfactory answer on my question. Return type from a Comparator

Your comparator is inconsistent : `compare(a,b)` and `compare(b,a)` both return `-1`. Whatever the internals are, the result will be inconsistent too. — Hugues M., Aug 25 '17 at 14:45
This is real crazy... Plz read carefully what comparator does. In essentials it's just how you compare two given values. When you set -1:-1 you just broke it, now it always returns 'less than'. — vk23, Aug 25 '17 at 14:46
To answer this, one should know exactly which algorithm is used. A look at these posts should be useful to potential answerers : https://stackoverflow.com/questions/12228659/what-is-the-sorting-algorithm-for-java , — Pac0, Aug 25 '17 at 14:46
Also, if you have elements which are both "less than the other", you should not be able to rely on whatever you imagine the result would be. So the fact that you get weird results is **not** surprising. — Pac0, Aug 25 '17 at 14:47
moreover, to cite a comment on my linked question, : "It's also worth noting that while the Oracle/Sun implementation referenced uses those algorithms, they're not required by the specification, and may differ in other implementations - http://docs.oracle.com/javase/6/docs/api/java/util/Arrays.html – Marc Bollinger Sep 1 '12 at 14:45 — Pac0, Aug 25 '17 at 14:47

score 3 · Answer 1 · edited Jun 20 '20 at 09:12

From the javadoc of Comparator:

In the foregoing description, the notation sgn(expression) designates the mathematical signum function, which is defined to return one of -1, 0, or 1 according to whether the value of expression is negative, zero or positive.

The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y. (This implies that compare(x, y) must throw an exception if and only if compare(y, x) throws an exception.)

The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0.

Finally, the implementor must ensure that compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z.

Your implementation breaks these assumptions: As you always return -1, you break at least the first assumptions:

sgn(compare(x, y)) == -sgn(compare(y, x)) does not hold if you always return -1: sgn(compare(x, y)) == sgn(compare(y, x)) for all x and y.

This leads to undefined behavior since the sort code relies on you correctly adhering to this contract.

score 0 · Answer 2 · answered Aug 25 '17 at 14:49

You did not break it. What you did is that you are telling the Comparator no matter what you compare it is always lower to the comparable value. For example if you use it like this

 Integer[] input = {
     1, 6, 8, 2, 10
 };
 List < Integer > inputList = Arrays.asList(input);
 Collections.sort(inputList, (a, b) - > a > b ? -1 : -1); // both are negative.
 System.out.println(inputList);

It will print [10, 2, 8, 6, 1]. It reverts the list since it starts by comparing from left-to-right.

score 0 · Answer 3 · answered Aug 25 '17 at 14:53

This Comparator implementation doesn't respect the specification of Comparator.compare() :

Collections.sort(inputList,(a,b)->a>b?-1:-1); // both are negative.

The specification states that :

the implementor must ensure that (compare(x, y)) == -sgn(compare(y, x)) for > all x and y.

In your implementation, you don't have this equality but this one :

sgn(compare(x, y)) == sgn(compare(y,> x))

Not respecting the contract of the method can give unpredictable results as the Collection methods manipulate your object.

Internals of Collections.sort in java

3 Answers3