Actually, in SQL OLAP, there's a built-in MDX function for MEDIANThat was to be my second answer: for a billion rows I'd use Oracle, since Oracle PSQL has a MEDIAN expression. ;-)
But perhaps the best answer would be that if you really need to do stats on resultsets of that magnitude you'd have to consider one of the specialist big-iron stats packages rather than trying to roll your own.
"... They ne'er cared for us
yet: suffer us to famish, and their store-houses
crammed with grain; make edicts for usury, to
support usurers; repeal daily any wholesome act
established against the rich, and provide more
piercing statutes daily, to chain up and restrain
the poor. If the wars eat us not up, they will; and
there's all the love they bear us."
-- Shakespeare: Coriolanus, Act 1, scene 1
