On Mon, Jul 1, 2013 at 4:31 PM, Claudio Freire <klaussfreire(at)gmail(dot)com> wrote:
> What?
>
> A median of medians algorithm will guarantee floor(N/2) elements on
> the smaller. That's the definition of median.
>
> Note that I'm referring to picking the actual median of all tuples,
> not just a sample. That's slow, but it guarantees O(n log n).
Ah, OK. Well, yes, that would guarantee O(n lg n). But, as you say,
it would be slow. :-)
--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company