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-t

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!