Standard Forth versus Python: a case study

[Fredrik Lundh]

Paul McGuire wrote:

> 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.)

if you absolutely definitely cannot afford to modify or copy the input data set, but can
read the data sequentially multiple times reasonably fast, you can do what's basically a
binary search for the median, by counting how many values you have that's above or
below the current guess, and repeating until you find the right value.  see e.g.

    http://ndevilla.free.fr/median/median/src/torben.c

</F>