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/