Comparator not sorting -2147483648 properly

Question

Trying to sort [5,3,9,-2147483648,2] using comparator where the values are TreeNodes

Structure of TreeNode:

public class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
 }

Below is my code :

Collections.sort(list,new Comparator<>(){
            public int compare(TreeNode a,TreeNode b)
            {
                return a.val-b.val;
            }
        });

Here list is collection of TreeNodes

Actual Output : 2,3,5,9,-2147483648

Expected Output : -2147483648,2,3,5,9

Try printing what e.g `9 - (-2147483648)` is or `(-2147483648) - 9`. — luk2302, Oct 15 '21 at 10:36
In short: use `Integer::compare` when comparing integers. Do not use arithmetic, as it is subject to overflow. — MC Emperor, Oct 15 '21 at 10:47

score 4 · Answer 1 · answered Oct 15 '21 at 10:39

return a.val-b.val;

This, like all integer arithmetic, is subject to overflow if the operands are too large.

Instead, you can use:

return Integer.compare(a.val, b.val);

Or, better, construct the Comparator using the helper method:

list.sort(Comparator.comparingInt(a -> a.val));

score 1 · Answer 2 · answered Oct 15 '21 at 11:11

So this happens because the result of the arithmetic operation overflows the max number allowed by Integer.

When doing the comparison at some point the loop does return 9 - (-2147483648) returning 2147483657 which is greater than the max value supported by integers 2147483647.

The best option to avoid these scenarios is using the method Integer.compare(a,b) provided by Java as @andy-turner mentions in his answer.

Comparator not sorting -2147483648 properly

2 Answers2