# Are there any estimated, imperfect or fuzzy sorting algorithms?

I'm implementing some estimation metrics that take samples of optimisation functions and estimate their properties. One of the metrics requires the data to be sorted; however, since the metric is only an estimation, I was wondering if I could get a comparatively accurate result if the data wasn't sorted precisely, but well enough.

I would expect data could be nearly sorted in less time than actually sorting it. However, I can't find any algorithms that will do this, which I find rather odd, so I thought I'd ask around here.

My idea of "imperfectly sorted" is quite loose. It could, for example, mean:

• Many elements are perfectly sorted, but some are not
• Adjacent elements are not necessarily in the correct order, but when comparing groups of elements, the elements increase on average; if plotted, there would be a visible general upwards trend

For the first definition above, I suppose you could take a sub-sample of the data and just quick-sort that, but I don't imagine it'll get you much of a performance improvement without seriously reducing the quality of the estimation.

It might also be possible to take something like quicksort and limit the depth of the recursion.

Do imperfect sorting algorithms exist? Can they significantly out-perform regular sorting algorithms?

• Using a standard algorithm with decent performance for lots of equal items with a lax equivalence relation sounds tempting until you start pondering transitivity. – greybeard May 26 '18 at 16:21
• (Searching for approximate sorting makes me think the topic was more popular in the nineties.) – greybeard May 26 '18 at 16:25
• (Was about to edit tag approximation into your post - see for yourself and decide about including approximate in the title, too.) There are attempts to speed up sub-quadratic sort procedure by stopping at a limited amount of disorder and remove that by a quadratic procedure - too lazy to think up a proper search. – greybeard May 26 '18 at 16:33
• @greybeard Seems like approximation is the correct term here, yes. If I could remember to include it in my search, I would have probably discovered the existing algorithms without the need to post this question :) Feel free to edit the title and tags though. – Phlippie Bosman May 28 '18 at 7:42

You can, in fact, make it somewhat faster than full sorting. Giesen, Schuberth, and Stojaković showed that you can get $n$ elements sorted to a Spearman distance (*) of $\frac{n^2}{\nu(n)}$ in $O(n \min(\log n, \log \nu(n)))$. So the more you're willing to sacrifice accuracy (the smaller you make $\nu(n)$), the faster the algorithm can run.