Algorithm 616: fast computation of the Hodges-Lehmann location estimator

A N function subprogram for computing the Hodges-L e h m a n n [5] estimator ~---m e d i a n { ( X ' + X J ) l < i < j < n } . l (1) ~ -~ This robust and highly efficient estimator [2] has not been widely used by statisticians because its apparent time computational complexity is O(n ~ log n). I m p r o v e m e n t s in computing ~ have previously been made with an iterative algorithm [11] and with some fast theoretical techniques [7, 8]. H L Q E S T is exact and fast, with expected time complexity of O.(n log n). T h e estimator ~ arises from inverting the one-sample Wilcoxon test statistic. T h a t is, ~ is a root of 0 = W(tt) = ~ rank(I X, -g I) x sign(X, -tt),