What sort does Java Collections.sort(nodes) use?

java collections sorting time-complexity mergesort
Kyle Jones picture Kyle Jones · Apr 15, 2009 · Viewed 23.6k times · Source

I think it is MergeSort, which is O(n log n).

However, the following output disagrees:

-1,0000000099000391,0000000099000427
1,0000000099000427,0000000099000346
5,0000000099000391,0000000099000346
1,0000000099000427,0000000099000345
5,0000000099000391,0000000099000345
1,0000000099000346,0000000099000345

I am sorting a nodelist of 4 nodes by sequence number, and the sort is doing 6 comparisons. I am puzzled because 6 > (4 log(4)). Can someone explain this to me?

P.S. It is mergesort, but I still don't understand my results.

Thanks for the answers everyone. Thank you Tom for correcting my math.

Answer

Andy Mikula picture Andy Mikula · Apr 15, 2009

O(n log n) doesn't mean that the number of comparisons will be equal to or less than n log n, just that the time taken will scale proportionally to n log n. Try doing tests with 8 nodes, or 16 nodes, or 32 nodes, and checking out the timing.

Related questions

Sort a Map<Key, Value> by values

I am relatively new to Java, and often find that I need to sort a Map<Key, Value> on the values. Since the values are not unique, I find myself converting the keySet into an array, and sorting …

Read More
How to sort an ArrayList?

I have a List of doubles in java and I want to sort ArrayList in descending order. Input ArrayList is as below: List<Double> testList = new ArrayList(); testList.add(0.5); testList.add(0.2); testList.add(0.9); testList.add(0.1); testList.add(0.1); testList.…

Read More
How to sort an ArrayList in Java

I have a class named Fruit. I am creating a list of this class and adding each fruit in the list. I want to sort this list based on the order of fruit name. public class Fruit{ private String fruitName; …

Read More