lkml.org 
[lkml]   [2001]   [Mar]   [10]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
SubjectRe: quicksort for linked list
From
Date
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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 13:29    [from the cache]
©2003-2011 Jasper Spaans