# Java sorting list of array vs sorting list of list

I have a list of points where each point is a tiny list of size `2`. I want to sort the list of points in increasing order of `x` and if `x` values are equal, I break tie by sorting in decreasing order of `y`.

I wrote a custom comparator to sort the points like this:

```Collections.sort(points, (a, b) -> {
if (a.get(0) != b.get(0)) {
return a.get(0) - b.get(0);
} return b.get(1) - a.get(1);
});
```

Here’s the input before sorting:

```(2, 1000)
(9, -1000)
(3, 15)
(9, -15)
(5, 12)
(12, -12)
(5, 10)
(10001, -10)
(19, 8)
(10001, -8)
```

Here’s the result produced after sorting with the above comparator:

```(2, 1000)
(3, 15)
(5, 12)
(5, 10)
(9, -15)
(9, -1000)
(12, -12)
(19, 8)
(10001, -10)
(10001, -8)
```

Observations:

1. The input is sorted in ascending order on `x`.
2. `(5, 12)` was correctly put before `(5, 10)`.
3. `(9, -15)` was correctly put before `(9, -1000)`.
4. However, `(10001, -10)` was put before `(10001, -8)`. Even though `-8` is larger than `-10`.

Feel like I am missing something trivial. I experimented with a few other ways of writing the comparator like using `Integer.compare(a, b)` or just `a.compareTo(t)`, but got the same result.

Finally, I changed the representation of point from `List<Integer>` to `int[]` and wrote the same comparator again. See results below:

```Collections.sort(points, (a, b) -> {
if (a != b)
return a - b;
return b - a;
});
```

Input before sorting:

```(2, 1000)
(9, -1000)
(3, 15)
(9, -150
(5, 12)
(12, -12)
(5, 10)
(10001, -10)
(19, 8)
(10001, -8)
```

After sorting:

```(2, 1000)
(3, 15)
(5, 12)
(5, 10)
(9, -15)
(9, -1000)
(12, -12)
(19, 8)
(10001, -8)
(10001, -10)
```

So list of arrays is getting sorted correctly as `(10001, -8)` was correctly put before `(10001, -10)`.

I am not able to understand why changing the representation of point resolved the issue and hence this question. I can give more details on how I am creating the List of points if required.

I am missing something trivial

Method `equals()` should be used for object comparison. Double equals `==` checks whether two references point to the same object in memory.

If you change the condition inside the comparator to `!a.get(0).equals(b.get(0))` it will work correctly.

However, (10001, -10) was put before (10001, -8). Even though -8 is larger than -10.

The reason for such behavior is that JVM caches all the instances of `Integer` (as well as `Byte`, `Short` and `Long`) in the range `[-128; 127]`. I.e. these instances are reused, the result of autoboxing of let’s say `int` with a value of `12` will be always the same object.

Because small values in your example like `3`, `5`, `12` will be represented by a single object, they were compared with `==` without issues. But the result of comparison with `==` for two `Integer` instances with a value of `10001` will be `false` because in this case there will be two distinct objects in the heap.

The approach of caching frequently used objects is called the Flyweight design pattern. It’s very rarely used in Java because this pattern can bring benefits when tons of identical objects are being created and destroyed. Only in such a case caching these objects will pay off with a significant performance improvement. As far as I know, it’s used in game development.

### Use the power of objects

`Point` must be an object, not a list, as Code-Apprentice has pointed out in his answer. Use the power of objects and don’t overuse collections. It brings several advantages:

• class provides you a structure, it’s easier to organize your code when you are thinking in terms of objects;
• behavior declared inside a class is reusable and easier to test;
• with classes, you can use the power of polymorphism.

Caution: objects could be also misused, one of the possible indicators of that is when a class doesn’t declare any behavior apart from getters and its data is being processed somehow in the code outside this class.

Although the notion of point (as a geometrical object) isn’t complicated, there are some useful options with regard to methods. For example, you could make instances of the `Point` class to be able to check to whether they are aligned horizontally or vertically, or whether two points are within a particular radius. And `Point` class can implement `Comparable` interface so that points will be able to compare themselves without a `Comparator`.

### Sorting

With Java 8 method `sort()` was added to the `List` interface. It expects an instance of `Comparator`, and if element of the list implement comparable, and you want them to be sorted according to the natural order `null` can be passed as an argument.

If the specified comparator is null then all elements in this list must implement the Comparable interface and the elements’ natural ordering should be used.

So instead of using utility class `Collections` you can invoke method `sort()` directly on a list of points (assuming that `Point` implements `Comparable<Point>`):

```points.sort(null); // the same as   points.sort(Comparator.naturalOrder());
```

Also, you can create multiple custom comparators by utilizing `default` and `static` methods from the `Comparator` interface like comparingInt() and thenComparing().

(for more information on how to build comparators with Java 8 methods take a look at this tutorial)