More efficient sort algorithm?

Question

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

Answer 1

There are a lot of things which the efficiency of a sorting algorithm could depend on, but one thing to note is that in general, if you are sorting based on comparisons between elements, the fastest possible asymptotic runtime is Ω(n lg n).

It is, however, possible to construct a scenario where sorting can be done faster than n lg n, but this requires using more information than just comparisons. These are the so-called "linear sorts", which sort by using the value of the element rather than a comparison to another element. Examples of these are Bucket Sort, Counting Sort, and Radix Sort.

The first comparison method you provided does provide extra information, which might enable a faster sort speed, but only under constrained conditions. If, for example, you know that there are no duplicate values, and that every value between the minimum and maximum value is used exactly once, then you could perform a sort by:

1. Performing a linear search to find the minimum.
2. Comparing each element to the minimum and placing at the index given by the comparison method.

This method should take 2n = O(n) time. Of course, unless the objects contain extra information besides the integer value, you could just construct the range min..max directly. Also, if you can read the integer values of the elements, you could just implement a normal bucket or counting sort on them.

tl;dr: The fastest possible comparison based sort is Ω(n lg n). It is possible to sort faster when you can read the exact value of an element, but linear sorts are only work in certain constrained circumstances. In general you should just use your programming language's builtin sort.