Torben algorithm enhancement

[dewhisna]

This isn't an "issue", but an "enhancement" that others may find useful. First off, let me express my thanks for your collection of median algorithms. I was in need of a good median algorithm that was non-destructive without requiring a second copy of the data and that didn't require dynamic memory allocation and yet was decently fast for use in an embedded application with limited computing resources. The Torben algorithm you have featured here almost fit the bill.

Where the Torben algorithm, as presented, fell short was for even-sized datasets, where I needed it to be the true median between the center two elements, not a lower median. The fast median search blog mentions this, but says that in order to obtain the true median, the routine must be called twice, doubling the processing time. But at least for the Torben algorithm, this isn't true.

To get the true NIST median, simply change the exit return code from this:

    if (less >= half) return maxltguess;
    else if (less+equal >= half) return guess;
    else return mingtguess;

To this:

    if (less >= half) min = maxltguess;
    else if (less+equal >= half) min = guess;
    else min = mingtguess;
    if (n&1) return min;        // if n is odd, we are done
    if (greater >= half) max = mingtguess;
    else if (greater+equal >= half) max = guess;
    else max = maxltguess;
    return (min+max)/2;

This simply takes the upper median value, which it actually found in the search as well, and averages it with the lower median value that it was previously returning. The short-circuit check for an odd-n is optional and very slightly reduces execution time for the odd case, depending on the compiler and processor.

I don't know if this can be easily applied to the other algorithms or not. And I didn't submit this as a pull request because your repository was more of a comparison between the algorithms than a specific implementation for a single algorithm. But, I thought this should be mentioned somewhere along with the algorithm for others to reference.

[sarnold]

Thanks! Looks like a reasonable enhancement, could also be added to the docs as well. As you probably noticed I got busy and haven't touched this for a bit, but feel free to fork it. If I can finish up a couple work things quick enough I might have time to play...

[sarnold]

Actually I didn't remember it was there, but I just looked and there is already a section for that topic in the FAQ: http://sarnold.github.io/medians-1D/median_search.html

An update there and/or in the Torben section would make sense.