Fast median search: an ANSI C implementation (1998)

The algorithm described as Torben's appears much earlier in Numerical Recipes for Fortran as a multi pass median that was designed to calculate medians from tapes where the memory was smaller than the storage device. Numerical Recipes cites Knuth's TAoCP I believe. The NR implementation is called mdian2 (for easy searching)

>Every ANSI compliant C library comes with an implementation of a quicksort routine

Actually the standard doesn't require qsort() to be quicksort. For example, musl's implementation uses the smoothsort algorithm.

http://port70.net/~nsz/c/c11/n1570.html#7.22.5.2

http://git.musl-libc.org/cgit/musl/tree/src/stdlib/qsort.c?i...

Many of O(n) algo for median have one compromise: They either return only the upper or lower median when n is even. In some applications, we might want average of these two instead. Are there any efficient algorithm there? Obviously it can be done with two calls to O(n) algo but can it be done more elegantly, efficiently and in single pass?