Reliability and efficiency of algorithms for computing the significance of the Mann-Whitney test (Q638042)

A new algorithm is presented for the \(p\)-value computation for the Mann-Whitney test. If \(n\) and \(m\) are the sizes of the compared samples, the runtime complexity of the algorithm is \(O(m^2n)\). This algorithm is an improvement of the Pagano and Trichler algorithm and is much more robust with respect to the roundoff errors accumulation. It uses a shifted fast Fourier transform with carefully chosen shift to avoid summation of many small terms. An upper bound for the roundoff error of the algorithm is given. Performance of the algorithm is compared with other known algorithms for \(n,m\leq 5000\).