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?
Thanks for the answers everyone. Thank you Tom for correcting my math.