What is the time complexity of java.util.Collections.sort() method?

Question

I have written the following class:

public class SortingObjectsWithAngleField implements Comparator<Point> {       public int compare(Point p1, Point p2) {         double delta = p1.getAngle() - p2.getAngle();         if(delta == 0.00001)             return 0;         return (delta > 0.00001) ? 1 : -1;     } } 

Then, in my main() method, I have created a List to which I add some objects which has "X" and "angle" field.

I then use:

Collections.sort(list, new SortingObjectsWithAngleField()); 

What is the complexity of this sort method?

Answer 1

You could have read up the docs on Collections sort, but here it is for you:

The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n log(n) performance.

Your Comparator doesn't change this complexity, unless you do anything with loops over your collection in it, which you don't.

Answer 2

You should have found it in the API: n log(n).