Computing distances between partial rankings

We give two efficient algorithms for computing distances between partial rankings (i.e. rankings with ties). Given two partial rankings over n elements, and with b and c equivalence classes, respectively, our first algorithm runs in O(nlogn/loglogn) time, and the second in O(nlogmin{b,c}) time.