Java - List<Integer> sort, comparator and overflow

Question

I've the following code that sorts a list in a descending order

List<Integer> list=Arrays.asList(Integer.MAX_VALUE, -1);
list.sort((x, y) -> y-x);
System.out.println(list)

The result is

[-1, 2147483647]

Now, I know that I should not write y-x because it can cause overflow problem.

But the question is why is the output that? I believed the output would be [2147483647, -1] because -1 - Integer.MAX_VALUE is -2147483648, still a negative integer, ad the operation seems not be affected by overflow problem. What I did wrong?

Answer 1

As you can read in Oracle's Object Ordening Java Tutorial near the bottom of the page:

You might be tempted to replace the final return statement in the Comparator with the simpler:

return e1.number() - e2.number(); 

Don't do it unless you're absolutely sure no one will ever have a negative employee number! This trick does not work in general because the signed integer type is not big enough to represent the difference of two arbitrary signed integers. If i is a large positive integer and j is a large negative integer, i - j will overflow and will return a negative integer. The resulting comparator violates one of the four technical restrictions we keep talking about (transitivity) and produces horrible, subtle bugs. This is not a purely theoretical concern; people get burned by it.

The situation described here is what the OP encounters: the difference between the two integers is more than Integer.MAX_VALUE and will therefore overflow during comparison, resulting in an unexpected sorting.

Answer 2

I just did what exactly @Robin Topper told.

import java.util.*;
public class Test {
    public static void main(String... args) {
        List<Integer> list = Arrays.asList(Integer.MAX_VALUE, -1);
        list.sort((x, y) -> {
            System.out.println("x: " + x + " y: " + y);
            System.out.println("y - x = " + (y - x));
            return y - x;
        });
        System.out.println(list);
    }
}

And I got

x: -1 y: 2147483647
y - x = -2147483648
[-1, 2147483647]

And we can see that

List#sort(Comparator) applies values onto given Comparator in inverse order.

1. With a given Comparator,
2. When it's applies with -1 and 2147483647,
3. The (y - x) part (2147483647 - -1) overflowed as -2147483648 which is negative,
4. And it is true that -1 is less than 2147483647.

Here's the sourcecodes.

List#sort(Comparator)

@SuppressWarnings({"unchecked", "rawtypes"})
default void More ...sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
         i.set((E) e);
    }
}

Arrays#sort(Comparator)

public static void sort(int[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}

DualPovotQuicksort#sort()

Answer 3

Before we start you need to know that Comparator considers pair (x,y) as ordered according to its design if compare(x,y) < 0
(just like for natural (ascending) order: if x<y then x-y<0).

---

Integer overflow

In mathematical world, if x and y in pair (x,y) are in ascending order we can write it as x<y which can also be rewritten as x-y<0. Descending order can be represented as x>y which can be rewritten as x-y>0.
But such rewriting is possible only in mathematical world. In IT world numeric types like int have their min and max values, and if we will try to calculate values out of that range we will face integer overflow. Your example is one of that cases. If x = -1 and y = 2147483647 then comparator calculating y-x will return -2147483648

     y       -   x
(2147483647) - (-1) = -2147483648 

instead of positive 2147483648.

Because of that, incorrect (and negative) result is returned, making sorting algorithm "think" that values of x and y are in correct order.

Wait, if that result was mistake, then how we got as result elements in ascending order [-1, 2147483647]? Shouldn't that "incorrect" order be descending?

No, because Comparator returning y-x describes descending order. Take a look. Elements x and y used in any Comparator.compare(x,y) are considered to be in correct order when Comparator.compare(x,y)<0. If we use code of our comparator we will get y-x<0, in order words y<x (or simpler x>y).

It can also be easily observed if we change a little elements in list

List<Integer> list = Arrays.asList(-1, 2, 5);

where after sorting we will get

[5, 2, -1]

---

In short:

• sorting algorithm uses Comparator which describes descending order
• but since Comparator makes mistake (caused by integer overflow) it doesn't inform sorting algorithm about need to "change order" of -1 and 2147483647 so they stay at their positions.