maybe you could use a multi-pivot quicksort or an insertion sort where you drag and drop each new item into any position in an already-sorted subset

(upon further investigation that's what the cited "bucket sort" is actually)

Have you read Judea Pearl's paper on Theoretical Bounds on the Complexity of Inexact Computations? It's an old paper from 1976. The abstract is as follows:

Abstract-This paper considers the reduction in algorithmic complexity that can be achieved by permitting approximate answers to computational problems. It is shown that Shannon’s rate-distortion function could, under quite general conditions, provide lower bounds on the mean complexity of inexact computations. As practical examples of this approach, we show that partial sorting of N items, insisting on matching any non zero fraction of the terms with their correct successors, requires 0 (N log N) comparisons. On the other hand, partial sorting in linear time is feasible (and necessary) if one permits any finite fraction of pairs to remain out of order. It is also shown that any error tolerance below 50 percent can neither reduce the state complexity of binary N-sequences from the zero-error value of O(N) nor reduce the combinational complexity of N-variable Boolean functions from the zero-error level of 0(2N/N).

Never in a million years, but that's exactly the angle I'm approaching it at. I'll look it up, but it intuitively says similar to what I'm thinking. "Linear-time Sort-ish..." and I guess the "extra" work is performing the comparison for the new item to insert and validating the comparison (implicitly) by confirming the order of the "extra" items you're compared against.

When humans are tasked with the comparison, it doesn't have to be strictly pair-wise and instead can devolve (kindof) into the various kinds of "sorting networks" that minimize the cmp-swap given a limited subset of the list.

Thanks for the reference!