I'm looking for an algorithm, which could perform better, than `Arrays.sort()`.
I know this will look like a silly question asked million times, but please read on. 

Let's have two classes implementing `Comparable` whose natural ordering is based on an int value. The first `compareTo` method looks like this: 

```
 public int compareTo(ComparableInteger o) {
     return this.value - o.value;        
 }

```

The second is this: 

```
public int compareTo(ComparableInteger o) {
    if (this.value > o.value) {
        return 1;
    } else {
        if (this.value == o.value) {
            return 0;
        } else {
            return -1;
        }
    }
}

```

When I call `Collections.sort` on list of instances of these clases, they both perform about the same. 

**My question is if there is a sorting algorithm, which would benefit of the added information of the first `compareTo` method.**
In the first example, the added information is this: 

Let's have three values of `ComparableInteger`:

```
a == 1
b == 2
c == 3

```

Now when we compare `c` to `a`, we get 2 and when we compare `c` to `b` we get 1. From the `compareTo` implementation it is clear, that the `b` should go after `a`, because `c.compareTo(a) > c.compareTo(b)` so we know the correct order. The existing `Comparable` contract doesn't require this and needs another comparison. For example following implementation also fulfills(at least I hope) the contract, but gives different result(numbers sorted, but even numbers are before odd numbers)

```
public int compareTo(ComparableInteger o) {
    if (value % 2 == o.value % 2){
        return value - o.value;
    } else {
        if (value % 2 == 1){
            return 1;
        }else{
            return -1;
        }
    }
}

```

* I'm well aware that the first example is not sound, because the int may overflow