Work-in-place

In computer science, algorithms work-in-place if they transform a data structure without requring extra memory (or disk) space. The input is overwritten with the output.

For example, sorting algorithms that can rearrange arrays into a desired order in-place include:

• Bubble sort
• Comb sort
• Selection sort
• insertion sort
• Heapsort
• Smoothsort
• Quicksort
• Shell sort

In computational complexity theory, in-place algorithms have O(1) space complexity.

Functional programming languages often discourage or don't support in-place algorithms that overwrite data (rather than merely constructing new data). This is a type of side effect. Note that it is possible in principle to carefully construct in-place algorithms that don't modify data (unless the data is no longer being used), but this is rarely done in practice. See purely functional data structures[?].