which sorting algorithms give near / approximate sort sooner?

Question

Which sorting algorithms produce intermediate orderings which are good approximations?

By "good approximation" I mean according to metrics such as Kendall's tau and Spearman's footrule for determining how "far" an ordered list is from another (in this case, the exact sort)

The particular application I have in mind is where humans are doing subjective pairwise comparison and may not be able to do all n log n comparisons required by, say, heapsort or best-case quicksort.

Which algorithms are better than others at getting the list to a near / approximate sort sooner?

Answer 1

You may want to check out the shell sort algorithm.

AFAIK it is the only algorithm you can use with a subjective comparison (meaning that you won't have any hint about median values or so) that will get nearer to the correct sort at every pass.

Here is some more information http://en.wikipedia.org/wiki/Shell_sort

Answer 2

I would suggest some version of quicksort. If you know in what range the data you want to sort is then you can select pivot elements cleverly and possibly divide the problem into more than two parts at a time.