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/
This archive was generated by hypermail 2b29 : Sat Mar 10 2001 - 11:26:37 EST