Very good question. I'm away from my work station so I can't do additional profiling, but my overall experience is that TreeSet is hella slow in almost every case.

My hunch is that the extreme indirection makes mince out of data locality during traversal, since TreeSet is backed by a red black tree, so conversion to list is O(n) cache misses, whereas the sorting algorithms are reasonably well behaved from a cache perspective (Java uses a dual pivot quicksort for primitives and TimSort for objects IIRC).