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

collectionsjavamergesortsortingtime-complexity

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.

Best Solution

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.