Collections.sort in java 8 does not work like java 6, and the comparator returns 0

Question

I recently upgraded our jdk application from Java 6 to Java 8, but still kept the source language level as Java 6. After changing one of our unit tests, it crashed. I noticed that Collections.sort for LinkedList works differently in Java 8 and Java 6. Even when I am the original level of java 8 with JDk 1.8, I have the same behavior. To recreate the problem: Listing Definition below:

public enum Weight { A(1), B(0), C(0), D(0), E(2); public int getWeight() { return weight; } private int weight; Weight(int weight) { this.weight = weight; } @Override public String toString() { return name() + '(' + weight + ')'; } } 

and main class as below:

 public class Main { public static void main(String[] args) { List<Weight> weightList = new LinkedList<Weight>(); weightList.add(Weight.A); weightList.add(Weight.B); weightList.add(Weight.C); weightList.add(Weight.D); weightList.add(Weight.E); Collections.sort(weightList, new Comparator<Weight>() { @Override public int compare(Weight o1, Weight o2) { return o1.getWeight() > o2.getWeight()? 1:0; } }); System.out.print(weightList); } } 

Output for running code under Java 6: "C: \ Program Files \ Java \ jdk1.6.0_45 \ bin \ java"

[B (0), C (0), D (0), A (1), E (2)]

and output for running code under java 8:

"C: \ Program Files (x86) \ Java \ jdk1.8.0_161 \ bin \ java"

[A (1), B (0), C (0), D (0), E (2)]

I changed the type from LinkedList to ArrayList , and I get the same result, but if I change the comparator as shown below, then Java 8 will sort the array:

 Collections.sort(weightList, new Comparator<Weight>() { @Override public int compare(Weight o1, Weight o2) { return o1.getWeight() > o2.getWeight()? 1:-1; } }); 

As you can see, it seems that java 8 is not sorting the code correctly. Is there a bug in Java or am I missing something as usual?

Answer 1

The internal sorting algorithm has been changed to Tim Sort for objects and a two-second quicksort for primitives , like from JDK 7.

Since your comparator was wrong (it returned 0 for unequal values), you are very lucky that it did not break earlier. Now it breaks as expected.

Answer 2

 public int compare(Weight o1, Weight o2) { return o1.getWeight() > o2.getWeight()? 1:0; } 

This definition does not match the contract expected by the Java API . sort behavior is undefined if you pass it an invalid Comparator .

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

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

• Finally, the developer must ensure that compare(x, y)==0 means that sgn(compare(x, z))==sgn(compare(y, z)) for all z .

Your function does not return -1 if o1 < o2 . It returns 0 , incorrectly stating that the arguments are equal. This also causes the first bullet to crash: if you flip the arguments, the result should change sign.

Correct implementation:

 public int compare(Weight o1, Weight o2) { return Integer.compare(o1.getWeight(), o2.getWeight()); } 

Answer 3

As Boris said in his comment: your compare() method is incorrect.

Look at your implementation:

  return o1.getWeight() > o2.getWeight()? 1:0; 

Suppose you have three objects in your list:

• o1: weigth 3
• o2: weigth 5
• o3: weigth 5

Now suppose that sort() calls thus compare() for your list:

compare(o1, o2) returns 0

compare(o2, o3) returns 0

In terms of transitivity, this means that o1 , o2 and o3 are of the same order. You do not want me to guess. If it runs on Java 6, this is simply a “chance” of implementation, not the result you should reliably expect.

To solve your problem, you need to handle 3 cases (higher, incomplete or equal):

 @Override public int compare(Weight o1, Weight o2) { if (o1.getWeight() > o2.getWeight()){ return 1; } else if (o1.getWeight() < o2.getWeight()){ return -1; } return 0; } 

Which is equivalent to finally write: return Integer.compare(o1.getWeight(), o2.getWeight()) .

Note that a much better alternative and less error prone in Java 8 uses the Comparator.comparingInt() factory method and directly uses the sort() method that was introduced in the List :

 weightList.sort(Comparator.comparingInt(Weight::getWeight));