Fast algorithms for the calculation of Kendall's \(\tau\) (Q2488379)

Algorithms are proposed for calculation of Kendall's rank correlation with the mean time of calculation \(O(n\log n)\) (\(n\) being the sample size). A simpler version of the algorithm calculates \(\tau\) in the case when the observations have no ties (duplications). A more complicated algorithm for the data with ties is also presented. The algorithms are based on fast sorting and balanced binary trees.