An in-place algorithm is an algorithm that transforms its input within the storage already occupied by that input, using little additional working memory. Under a strict and common definition, it uses only a constant number of extra machine words, independent of input size. Some conventions also describe algorithms with a logarithmic amount of auxiliary storage, particularly a recursive call stack, as in-place. The term therefore requires an explicit storage convention: modifying the original data does not, by itself, establish that an algorithm is in-place.
Definition and space accounting
The defining property concerns auxiliary space: memory used in addition to the input storage and any output storage that the computational model explicitly excludes. This is distinct from total space complexity. An algorithm operating in-place on an array of elements still has access to the array’s storage; its additional working memory may nevertheless be constant.
Under the strict definition,
machine words, where is the input size. A few index variables and a temporary value for exchanging two elements normally satisfy this requirement.
Several accounting choices matter:
- Machine words versus bits. In a conventional random-access machine model, a word is large enough to hold an input address. An index into positions therefore requires bits. Constant-word auxiliary space is not necessarily constant-bit auxiliary space.
- Call-stack storage. Parameters, local variables, and saved execution state in active function calls consume memory. A recursive procedure does not have constant auxiliary space merely because it allocates no explicit buffer.
- Output storage. Definitions of auxiliary space sometimes exclude a separate output area. However, an algorithm that constructs a complete replacement array is normally called out-of-place, even when its accounting convention excludes that array from working storage.
- Element representation. A temporary element occupies constant space when elements are fixed-size values or references. Copying a variable-sized object can require additional storage proportional to that object’s size.
An out-of-place algorithm, by contrast, produces a transformed representation in separate storage rather than reusing the input representation as its principal destination.
How in-place computation works
An in-place transformation must preserve information until it is no longer needed. Overwriting a value prematurely can destroy input required by a later step.
Common techniques include:
- Swapping: exchanging elements with one temporary location.
- Shifting: moving elements into positions that have become available.
- Cycle processing: following a cycle of a permutation while retaining one displaced value.
- Compaction: maintaining separate read and write positions so that retained elements overwrite positions no longer needed.
- Pointer rearrangement: changing links in a linked list instead of allocating replacement nodes.
For example, an array can be reversed by exchanging its first and last elements, then its second and next-to-last elements, continuing toward the center.
reverse(A, n):
left = 0
right = n - 1
while left < right:
temporary = A[left]
A[left] = A[right]
A[right] = temporary
left = left + 1
right = right - 1
This procedure performs exchanges, has time complexity, and uses auxiliary words for fixed-size elements.
Its correctness can be expressed through a loop invariant: before each iteration, positions outside the interval from left to right already contain their final values, while the remaining interval still contains the elements that must be reversed.
Sorting algorithms
In-place computation is especially important in sorting, where allocating a second array can substantially increase peak memory use.
| Algorithm or implementation | Auxiliary space | Important qualification |
|---|---|---|
| Standard iterative [[insertion-sort | insertion sort]] | |
| [[heapsort | Heapsort]] with iterative heap adjustment | |
| Conventional recursive [[quicksort | quicksort]] with in-place partitioning | Expected , worst-case stack space under usual randomized analysis |
| Quicksort that recurses only on the smaller partition and iterates over the larger | stack space in the worst case | Bounds recursion depth, but does not eliminate quadratic worst-case running time. |
| Conventional array [[merge-sort | merge sort]] | |
| Specialized in-place merging methods | Depends on the method | Can reduce or eliminate the external buffer, often with greater implementation complexity. |
Quicksort illustrates why terminology varies. It is widely called in-place because its partitioning rearranges the original array without a second array. Under a strict constant-auxiliary-space definition, however, the usual recursive implementation does not qualify.
Storage use and stability are separate properties. A stable sort preserves the original relative order of elements with equal keys. Standard insertion sort can be both stable and in-place; standard heapsort is in-place but generally unstable. Stable in-place merging and sorting are possible, although combining stability, low storage use, and efficient running time requires more sophisticated methods.
Other applications
Array compaction
Filtering an array can be performed with a read index and a write index. Each retained element is copied to the next write position, and the procedure returns the length of the retained prefix.
For a single-pass, order-preserving implementation, the write index never advances beyond the read index. This prevents a write from destroying an unread element. The physical allocation may remain unchanged even though the logical sequence becomes shorter.
Removing duplicates from a sorted array uses a similar technique.
Matrix transformations
A square matrix can be transposed in-place by exchanging entries across its main diagonal. For an matrix,
Transposing a rectangular matrix stored in one contiguous array is more involved. The destination mapping can contain longer permutation cycles, and locating or tracking those cycles without extra storage complicates the algorithm.
Linked structures
A singly linked list can be reversed using a constant number of node references: previous, current, and next. Each link is redirected after the original successor has been saved.
This changes the existing data structure rather than constructing a replacement list. Whether such mutation is permitted depends on ownership and whether other parts of the program retain references to the same nodes.
Dynamic programming
Some dynamic programming algorithms reuse storage when older states are no longer needed. A full table may be reduced to a few rows or a single row.
Such a reduction is not automatically in-place: the remaining workspace may still grow with input size. Update order also matters. Overwriting a state before all dependent computations have used it can change the recurrence being evaluated.
Mutation, interfaces, and implementation
“In-place” describes storage behavior, whereas mutation describes a change to an existing object. The concepts overlap but are not equivalent.
A function may modify its input only after building a complete temporary result. Its interface is mutating, but its implementation is not a constant-space in-place algorithm. Conversely, an in-place function may return a reference to the modified object; returning a value does not imply that a separate result was allocated.
Aliasing makes mutation observable through other references to the same storage. Shared data can also require synchronization when accessed by multiple threads. An in-place implementation is not inherently safe for concurrent use.
In environments with immutable values or copy-on-write storage, an operation that appears to update an object may trigger a copy. Actual storage use therefore depends on both the algorithm and the runtime representation.
Benefits and limitations
In-place algorithms can reduce peak memory requirements and avoid allocating and copying a full replacement representation. These properties are useful for large inputs and memory-constrained systems.
Low auxiliary space does not guarantee high speed. An in-place method may perform more comparisons, writes, or irregular memory accesses than an out-of-place alternative. Its interaction with the CPU cache can be favorable or unfavorable depending on access patterns. Separate buffers can also simplify parallel computation by giving independent operations distinct output regions.
Destructive updates introduce additional constraints:
- The original input is not automatically preserved.
- Failure partway through an operation may leave a partially transformed state.
- Rollback or strong exception guarantees may require logging, copies, or other additional storage.
- Reducing memory use can increase running time or implementation complexity.
A precise description therefore states the auxiliary-space bound, whether it is measured in words or bits, whether recursive stack frames are counted, and which input or output regions may be overwritten.