<p>From time to time I browse the web and look for interesting algorithms and datastructures to put into my bag of tricks. A year ago I came across the <a href="http://en.wikipedia.org/wiki/Soft_heap" rel="noreferrer">Soft Heap</a> data-structure and learned about near sorting.</p>

<p>The idea behind this is that it's possible to break the O(n log n) barrier of compare based sorts if you can live with the fact that the sort algorithm cheats a bit. You get a almost sorted list but you have to live with some errors as well.</p>

<p>I played around with the algorithms in a test environement but never found a use for them. </p>

<p>So the question: Has anyone ever used near sorting in practice? If so in which kind of applications? Can you think up a use-case where near sorting is the right thing to do? </p>

This is a total flying guess, but given the inherent subjectivity of "relevance" measures when sorting search results, I'd venture that it doesn't really matter whether or not they're perfectly sorted. The same could be said for recommendations. If you can somehow arrange that every other part of your algorithm for those things is O(n) then you might look to avoid a sort.
Be aware also that in the worst case your "nearly sorted" data
does not
meet one possible intuitive idea of "nearly sorted", which is that it has only a small number of inversions. The reason for this is just that if your data has only O(n) inversions, then you can finish sorting it in O(n) time using insertion sort or cocktail sort (i.e. two-way bubble sort). It follows that you cannot possibly have reached this point from completely unsorted, in O(n) time (using comparisons). So you're looking for applications where a majority subset of the data is sorted and the remainder is scattered,
not
for applications requiring that every element is close to its correct position.