which sorting algorithms give near / approximate sort sooner?
algorithm, language-agnostic, sorting
Solution
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
Problem
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?