Algorithm 616: fast computation of the Hodges-Lehmann location estimator
John F. Monahan · ACM Transactions on Mathematical Software · 1984
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),where W(g) is the Wilcoxon test statistic for the hypothesis H:E(XI) ffi tt.NoticeThe me&an for an even number of values is always taken to be the average of the two middle values.