Are there sorting algorithms that take advantage of a metric space?

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.

For the searching problem (rather than sorting), your idea sounds like interpolation search. Binary search uses only the binary result of the comparison (less than or not), and runs in $O(\lg n)$ time. Interpolation search also uses information about how close the values were, and heuristically runs in $O(\lg \lg n)$ time in the average case. Thus, that's an example where using the extra information can speed up search (at least heuristically).

StackExchange Computer Science Q#54272, answer score: 3