Messages in this thread |  | | | Subject | Re: quicksort for linked list | | From | Jerome Vouillon <> | | Date | 10 Mar 2001 11:15:32 -0500 |
| |
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/
|  |