We know comparison sorting algorithms use the ternary information (lt, eq, gt) garnered from a single comparison to make decisions about what to do next. Is there any research into using a metric? That is, if we compare $x$ and $y$ and we not only know that $y > x$ but we also know the value $y - x$. Presumably if $y - x$ were a very large number we could heuristically separate them from each other, or move $y$ closer to end of the array, or move $x$ closer to the beginning. Could you make fewer than $O(n \lg n)$ comparisons in this way?This is not a very precise idea (and credit goes to my friend Ian who brought it up out of the blue one day), but I Googled around for a little bit and I was unable to find anything to help me narrow the question.
Are there sorting algorithms that take advantage of a metric space?
algorithms;sorting