Maybe have a parent function which passes in the array as 4k chunks/offsets and checks the return? 4k is a random size, there is probably a value which hits the sweet spot here.
True, I had hoped GCC would optimize that -- it doesn't :(.
It would make no sense for GCC to automatically add early-exit: that requires a judgement call about the vectors the function is intended to run on. A priori, the function might be intended to run on vectors that are almost always sorted, in which case the extra branch would be severely suboptimal.
I agree that the optimization isn't possible but this is for correctness reasons. The performance penalty of the extra branch is almost negligible due to branch prediction.