In-place algorithm

An algorithm works in-place or in situ if it except the for the storage of the required data to be processed memory only a constant, that is required by the independent data to be processed amount amount of memory. The algorithm overwrites the input data with the output data.

For example, the Bubblesort algorithm works in-place, while Bucketsort works out-of-place , because the output data has to be saved in a second list, which, however , does not affect the original data. The space complexity of place in-working algorithms, in Landau notation expressed . ${\displaystyle {\mathcal {O}}(1)}$

In purely functional programming languages , assignments cannot be carried out directly and it is therefore not easily possible to describe in-place algorithms there. However, by optimizing the compiler, out-of-place algorithms are automatically translated into equivalent in-place algorithms in some functional programming languages. For example, the Glasgow Haskell Compiler recognizes that after a modified copy of a variable has been created, the original is no longer used. In this case, the copy is implemented internally as an assignment and therefore no additional memory is used.