In-place algorithm

An in-place algorithm is a method for transforming data that rewrites the same memory the input already occupies, rather than building a separate copy to hold the result. Because it needs only a small, fixed amount of extra working space regardless of how large the input is, an in-place algorithm can process data using far less memory than an equivalent method that allocates a new structure for its output, which matters most when the input is very large or memory is limited. Classic sorting methods are commonly implemented in place, swapping elements within the original array as they work, while an algorithm that is not implemented this way is sometimes described as out-of-place, and instead requires additional storage proportional to the size of the input.