[ghoul2]

Given that the comparison function doesn't have the transitive property (if line a > line b and line b > line c that implies line a > line c), does this sort really work?

The 'allpair' variant, which aggregates the score across all n*(n-1) comparisons will work, but the other two couldn't possibly have stable results - it would depend on the order of the items in the input.

[vagozino]

Yes, that's correct! All three techniques have their trade-offs. I like the term "stability" you are using for this. There's definitely interesting avenues to go about this trading number of comparisons vs. stability.