Re: quicksort for linked list

[Jerome Vouillon <vouillon@saul.cis.upenn.edu>]

Oliver Xymoron <oxymoron@waste.org> writes:

> On Fri, 9 Mar 2001, Rogier Wolff wrote:
> 
> > Quicksort however is an algorithm that is recursive. This means that
> > it can use unbounded amounts of stack -> This is not for the kernel.
> 
> It is of course bounded by the input size, but yes, it can use O(n)
> additional memory in the worst case. There's no particular reason this
> memory has to be on the stack - it's just convenient.

You only need O(log n) additional memory if you sort the shortest
sublist before the longest one (and turn the second recursive call
into a loop).
As log n is certainly less that 64, one can even consider that
Quicksort only uses a bounded amount of memory.

-- Jerome