you could at least move the array more to the middle ground (on average)

Pretending for a second that first doesn't require putting the contents of entire array on the stack, the performance would still be O(N).

Mind you, that's rarely a problem since most arrays are quite small, but the code is also much less readable.