Bubble sort scans the full array repeatedly until finished, but only along the pairwise edge, and usually finishes way early
So in an array of 20 elements you have a maximum of 380 comparisons
This searches Euler's Little Triangle the whole way every time, so in an array of 20 elements, you have a maximum of 380 comparisons again
Seems similar, right?
Except doing pairwise you're likely to exit without doing all 19 scans - at the logarithm if it's well distributed - so it probably does either 4 or 5 scans, saving ~80% of the work
The issue isn't the ceiling; it's the common floor
Doing it the seemingly-normal way radically changes the common floor
So not only does this do different comparisons, it "radically" changes the number of "common floor" work.
And by the way, there's something wrong with your analysis of the number of scans needed for the 20 element bubble sort. I don't understand your argument, but I did some experiments with a randomly distributed array. I never saw it sort in fewer than 12 scans, after a few dozen trials.
