Nicolas Alvarez <nic### [at] gmailisthebestcom> wrote:
> I once thought sorting a linked list would be even faster than an array, 

  It is, if copying one element is slow enough.

> 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...

  It is perfectly possible to implement merge sort and even quick sort
on a linked list without the need for random access. Merge sort is the
best for linked lists because it's truely O(n log n), has no pathological
cases, and for doubly-linked lists requires no additional memory. (The
array links can be used as the "additional memory" the merge sort algorithm
requires, so no additional memory needs to be allocated just for the
sorting.)

-- 
                                                          - Warp

Post a reply to this message