Sometimes performance just doesn't matter, compared to the idea behind a piece of code. The in-place C for loop example makes functional programming versions look bad when looked at strictly to performance, but the C for loop has traded meaning for concrete but naive performance.
In fact, the C for loop has so little "meaning" that compilers won't optimize them, without some explicit pragma to do so, out of fear of fucking them up just on aliasing alone. And then it generates basically the steps: is i < l? get at location i * sizeof(a) + a, multiply by 5, store at location i * sizeof(a) + a, increment i, repeat, etc. just run at a brute force execution speed expected of a program written in C.
On the other hand, a form with non-ambiguous meaning can be slow, but it does have meaning and a potential to have better instructions generated.
It's a waste of memory and time.
For sorting, I'd figure if the waste of memory was significant, it would not be a significant waste of time, and vice versa.
It's interesting that computations can be modeled without state and the lambda calculus etc., but it's all just mental masturbation.
Functional does not model without state though, functional simply doesn't hide state. Functional languages force state to be explicitly brought to the attention to the programmer, and forces him to take care of the stateful behavior all the way through the function. The real complexity of any location of code can be eyeballed right away by the number of arguments within all function scopes of that location. What is actually different about functional is non-destructive updates and immutability, this forces a different approach to computation with the benefit of added guarantees in larger concurrent systems. The lack of destructive updates requires one to become creative, this discourages concern of manipulation/curating of data and encourages relationship modeling of data. It is the forced writing of non-retarded code.
Imperative languages hide the real deal about state, and therefore hide real complexity, by not requiring any of this. On the other hand, sometimes the real complexity between objects is understood to be just too big (I'd say things like games would fall under this) and one ends up using something else and put up with the post facto extra debugging that may entail from it.
Given that, it is just one paradigm, it's not particularly great for some domains compared to other domains. I think it works best when the target design has a "tree shape".