RIGHT INVARIANT METRICS AND MEASURES OF PRESORTEDNESS

Right invariant metrics (ri-metrics) have several applications in the theory of rank correlation methods. For example, ranking models based on ri-metrics generalize Mallow's ranking models. We explore the relationship between right invariant metrics and measures of presortedness (mops). The latter have been used to evaluate the behavior of sorting algorithms on nearly-sorted inputs. We give necessary and sufficient conditions for a measure of presortedness to be extended to a ri-metric; we characterize those ri-metrics that can be used as mops; and we show that those mops that are extendible to ri-metrics can be constructed from sets of sorting operations. Our results provide a paradigm for the construction of mops and ri-metrics.