> So my feeling is we should just remove the swap_cnt code and return to
> the original B&M algorithm. Being much faster than expected for
> presorted input doesn't justify being far slower than expected for
> other inputs, IMHO. In the context of Postgres I doubt that perfectly
> sorted input shows up very often anyway.
>
> Comments?
Checking for presorted input is O(n).
If the input is random, an average of 3 elements will be tested.
So adding an in-order check of the data should not be too expensive.
I would benchmark several approaches and see which one is best when used
in-place.