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

scaleproportionally to n log n. Try doing tests with 8 nodes, or 16 nodes, or 32 nodes, and checking out the timing.