What does "in-place" mean exactly?

Question

I know there are other questions about the meaning of the "in-place" algorithm but my question is a bit different. I know it means that the algorithm changes the original input data instead of allocating new space for the output. But what I'm not sure about is whether the auxiliary memory counts. Namely:

• if an algorithm allocates some additional memory in order to compute the result
• if an algorithm has a non-constant number of recursive calls which take up additional space on the stack

Answer 1

In-place normally implies sub-linear additional space. This isn't necessarily part of the meaning of the term. It's just that an in-place algorithm that uses linear or greater space is not interesting. If you're going to allocate O(n) space to compute an output in the same space as the input, you could have equally easily produced the output in fresh memory and maintained the same memory bound. The value of computing in-place has been lost.

Wikipedia goes farther and says the amount of extra storage is constant. However, an algorithm (say mergesort) that uses log(n) additional space to write the output over the input is still in-place in usages I have seen.