4

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
Improve this question
6
  • 1
    This is the kind of nano-optimization that is unlikely to matter. I believe the algorithm underneath is quicksort. I'll bet you can't measure a performance difference. Commented Feb 6, 2015 at 15:33
  • Interesting question. It reminds me of radix sort. Commented Feb 6, 2015 at 15:33
  • Is this just curiosity, or have you profiled your code and came to the conclusion that the sort(...) method is a hot spot? Java's collections/array sorting algorithms are quick- and merge-sort, which both run in O(n*log(n)). There are faster sorting algorithms: stackoverflow.com/questions/17641858/linear-sorting-algorithms Commented Feb 6, 2015 at 15:33
  • It is just a curiosity. It always bugged me, that it doesn't matter if I return real difference or just 0/1/-1 Commented Feb 6, 2015 at 15:35
  • It does matter. The subtraction is broken because it can overflow. Commented Feb 6, 2015 at 16:09

5 Answers 5

Reset to default
4

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thanks!. I've tried radix sort on integers and it's about 2 times faster than Collections.sort. I'm just not sure if it's because of the algorithm or the objects overhead
2

Be careful with the first Comparison, it is not perfectly consistent. 

 public int compareTo(ComparableInteger o) {
     return this.value - o.value; //not always correct
 }

As Eric Lippert points out (the article is for C#, but still valid for Java), you first Comparison is unsafe:

In particular, for the inputs Int32.MinValue and Int32.MaxValue, the difference is 1. Clearly the smallest possible integer is smaller than the largest possible integer, but this method gives the opposite result!

As you mentioned, other overflow/underflow problems arise as well.

So in fact, it would take more logical overhead outside the comparison for any sorting algorithm to try to use the "extra" information. The "extra" information comes at the cost of some extra headaches and corner cases.

Improve this answer

4 Comments

It's unsafe in more corner cases... if I do Integer.MAX_VALUE - any negative int, then it will overflow.
@NeplatnyUdaj thanks. I made the wording more general.
But I've already mentioned that in the original post. I don't think that changes a lot about the question. It could be BigInteger...
@NeplatnyUdaj Like I mentioned, the "extra" information comes with the price of having to deal with the overflow/underflow problems. You'd have to keep your datatypes' size in mind and do extra logic to prevent the overflow/underflows for every iteration.
1

I don't think the extra information in the first compareTo is as useful as you think: in your example, you have merely replaced a comparison between objects with a comparison between results of compareTo, and that will be the case regardless of sorting algorithm.

Improve this answer

1 Comment

Looks like you're right. It could be only benefitial if the compareTo was expensive.
1

  • Normal algorithm: 3 comparisons

  • Your algorithm: 2 comparisons + 1 comparison of 'cached' values of previous differences. (in your example checking that 2>1 which will determine order of a and b)

As for O complexity they are the same, but my feeling is that your implementation will be bit slower in practice (and bit harder to implement).

Improve this answer

1 Comment

I see that now. It would be best to create a method getIntValue and sort based on that instead of compareTo. I really didn't think this through :)
0

Always stick with the core Java Collection features such as Arrays.sort() as they have been tested for all kinds of nuances that have been noted in the answers so far, that most programmers aren't likely to think of, and they are also tuned for performance. And when the next version of Java comes out, you won't have to re-test your own sort routine.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.