In-place algorithm

An algorithm operating in -place, or in situ if other than the required for the storage of the memory data to be processed, he only needs a constant, that is independent of the amount of data to be processed, quantity of memory. The algorithm overwrites the input data with the output data.

To work around the bubblesort algorithm in-place, while bucket sort out-of -place works because the output data must be stored in a second list, which, however, the original data remain unaffected. The space complexity of in-place operating algorithms is expressed in the Landau notation O (1).

In pure functional programming assignments can not be done right and it is there, therefore, not readily possible to describe in-place algorithms. However, out-of -place algorithms are automatically translated into equivalent in-place algorithms in some functional programming languages ​​by the compiler optimizations. For example, recognizes the Glasgow Haskell compiler, that after the generation of a modified copy of the original variable is no longer used. In this case, the copy is performed internally as an assignment and thus does not consume additional memory.

• Algorithm