>>> Of course, a good quicksort utterly depends on picking the right 
>>> pivot. And for a linked list, it seems hard to do that without 
>>> wasting too much time trying to pick a pivot. So I'm not really sure 
>>> quicksort is a good algorithm to be using on a linked list in the 
>>> first place, but hey...
>>
>> In Java, if you sort a linked list (or any collection with linear 
>> lookup time), it copies the whole contents into an array, sorts it, 
>> and copies the sorted results back to the structure you were using.
> 
> Ouch! That's a bit expensive isn't it?
> 
> Mind you... maybe not... A quick sort with a decent pivot is going to be 
> that much faster.

I once thought sorting a linked list would be even faster than an array, 
since moving elements around is so fast (no copying needed, just 
changing the link). Then pretty quickly noticed how stupid that was; you 
need to read elements to know *where* to move the elements, and reading 
random elements is not fast...

Post a reply to this message