From dsimcha at gmail.com  Sun Dec 13 06:38:05 2009
From: dsimcha at gmail.com (David Simcha)
Date: Sun, 13 Dec 2009 00:38:05 -0500
Subject: [Rd] O(N log N) Kendall Tau
Message-ID: <4B247DBD.6060002@gmail.com>

I've noticed that the implementation of Kendall's Tau in R is O(N^2).  
The following reference describes how it can be done in O(N log N):

 A Computer Method for Calculating Kendall's Tau with Ungrouped Data
 William R. Knight
 Journal of the American Statistical Association, Vol. 61, No. 314, Part 
1 (Jun., 1966), pp. 436-439
 http://www.jstor.org/pss/2282833

I'm interested in contributing an implementation of this algorithm to 
R.  However, I have a few questions:

1.  Would it likely be accepted if well-implemented?
2.  cov.c in the main/ directory of the R source tree seems to contain 
at least 4 different but nearly identical implementations of Kendall's 
Tau:  cov_complete1, cov_complete2, cov_na1, and cov_na2.  I can't tell 
why.  The file is very difficult to read because of its lack of 
comments, (ab)use of macros and improper indentation.  As I will 
probably need to modify this file, can some seasoned veteran please 
explain what the heck is going on in this file?



[Rd] O(N log N) Kendall Tau
David Simcha