Messages in this thread | | | Date | Sat, 10 Mar 2001 16:54:58 -0700 | From | Michal Jaegermann <> | Subject | Re: quicksort for linked list |
| |
On Sat, Mar 10, 2001 at 07:50:06PM +0100, Martin Mares wrote: > Hello! > > > Well, not really in this situation, after a simple modification. It is > > trivial to show that using "shorter interval sorted first" approach one > > can bound an amount of an extra memory, on stack or otherwise, and by a > > rather small number. > > By O(log N) which is in reality a small number :)
Assuming that we sort a full range of 32-bit numbers (pointers on a 32-bit CPU, for example, are numbers of that kind but usually a range can be narrowed down quite substantially) then with a bit of a careful programming you need, I think, something like 16 extra 4-byte words or maybe even a bit less. I do not remember precisely, as I was doing this exercise a long time ago, but even if this is 32, and you need carefuly constructed example to need them all these extra cells, I still think that this is not a huge amount of memory. Especially when every element of a list you are sorting is likely quite a bit bigger.
Exponents are something which grows these numbers pretty fast. :-)
Michal - 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/
| |