# 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.

• " Presumably if y−x were a very large number we could heuristically separate them from each other, or ..." -- not without assumptions about the distribution of values. – Raphael Mar 10 '16 at 21:03
• Say you knew an estimate of the distribution. Like you had min, Q1, Q2, Q3, max. Or say you even knew the distribution of the data, like you had an oracle that could tell you which percentile a certain value would be in with uncertainty. If we had a perfect oracle that told you with zero uncertainty the percentile, you could sort in linear time with some sort of bucket sort. I guess my question is what happens as you introduce more uncertainty. This might just be chasing moles down molehills. – hao Mar 10 '16 at 21:06
• – Gilles Mar 10 '16 at 21:06
• @Raphael I don't think you necessarily need to assume anything about the distribution of values. By the time you've read the whole input, you kind of know the distribution. – David Richerby Mar 10 '16 at 21:37

## 2 Answers

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).

It's possible to sort $n$ integers in $o(n\log n)$ time (the exact complexity might depend on the model). Wikipedia has a very thorough page on the topic.