Newbie: finding the key/index of the min/max element

[Alex Martelli]

David Eppstein wrote:
        ...
>> > list, I'm pretty sure it would usually be better just to sort the list
>> > and return the middle item, instead of using a linear-time median
>> > finding algorithm, despite the nonlinear big-O time of a sort.
>> 
>> No doubt -- for small-enough N.  Just as doublessly, there will be
>> an N above which the O(N) algorithm is preferable.
> 
> My impression is that precompiled can beat interpreted by as much as a
> factor of 100.  What is the N for which that beats an O(log N) factor?

I don't know, as I don't have a linear-time median finder lying around,
and I'm not going to code and debug one just for fun.  The sort method
of lists is so wonderfully well optimized that racing against it can be,
well, "interesting" (studying its C sources carefully after reading Tim 
Peter's introductory essay to the "searching and sorting" chapter of the 
Python Cookbook teaches a LOT about programming and optimizing,
IMHO -- which reminds me, I'd better drop c.l.py again and rush right
back to Cookbook editing *NOW*...).


Alex