The space consumed by the stack should absolutely be taken into consideration, but some may disagree here (I believe some algorithms even make complexity claims ignoring this - there's an unanswered related question about radix sort floating around here somewhere).
Since we split the array in half at each recursive call, the size of the stack will be O(log n)
.
So, if we take it into consideration, the total space will be O(n + log n)
, which is just O(n)
(because, in big-O notation, we can discard asymptotically smaller terms), so it doesn't change the complexity.
And for creating a local array, a similar argument applies. If you create a local array at each step, you end up with O(n + n/2 + n/4 + n/8 + ...) = O(2n) = O(n)
(because, in big-O notation, we can discard constant factors), so that doesn't change the complexity either.