Standard Forth versus Python: a case study

[Paul Rubin]

"Paul McGuire" <ptmcg at austin.rr._bogus_.com> writes:
> My original question was in response to your post, that sort() wasn't 
> required but only a temp variable.  I am very interested in seeing your 
> solution that does not require the data to be sorted.  (This is not just an 
> academic exercise - given a large historical data set, sorting the data is 
> one of the costliest parts of computing the median, and I would greatly 
> appreciate seeing an alternative algorithm.)

There are well known algorithms for finding the median in expected
O(n) time, the most straightforward of which is a modified quicksort.
You do the traditional quicksort pivot step, figure out which
partition the median is in, and recurse on just that partition instead
of on both of them.  Expected running time is n + n/2 + n/4 + ...
which is approx 2n.

Tarjan discovered a guaranteed O(n) algorithm in the 1970's(?) whose
operation is much different and quite complex.  But all of these need
more than one temp var.  See an algorithms book like CLRS or Knuth
for more info.