3
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ " 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. $\endgroup$
    – Raphael ♦
    Mar 10, 2016 at 21:03
  • 1
    $\begingroup$ 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. $\endgroup$
    – hao
    Mar 10, 2016 at 21:06
  • 2
    $\begingroup$ Related: Why can I look at a graph and immediately find the closest point to another point, but it takes me O(n) time through programming? $\endgroup$
    – Gilles 'SO- stop being evil'
    Mar 10, 2016 at 21:06
  • $\begingroup$ @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. $\endgroup$
    – David Richerby
    Mar 10, 2016 at 21:37

2 Answers 2

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.