Re: quicksort for linked list

[Helge Hafting <helgehaf@idb.hist.no>]

Manoj Sontakke wrote:
> 
> Hi
>         Sorry, these questions do not belog here but i could not find any
> better place.
> 
> 1. Is quicksort on doubly linked list is implemented anywhere? I need it
> for sk_buff queues.

I cannot see how the quicksort algorithm could work on a doubly
linked list, as it relies on being able to look
up elements directly as in an array.

You can probably find algorithms for sorting a linked list, but
it won't be quicksort.

You can however quicksort the list _if_ you have room enough for an
additional data structure:

1. find out how many elements there are.  (Count them if necessary)
2. Allocate a pointer array of this size.
3. fill the pointer array with pointers to list members.
4. quicksort the pointer array
5. Traverse the pointer array and set the links for each
   list member to point to next/previous element pointed
   to by the array.  Now you have a sorted linked list!

Steps 1,2,3 & 5 are all O(n), better than the O(nlgn) for
quicksort.  


Helge Hafting