In-place algorithm

An algorithm that uses only a small, input-size-independent amount of extra storage, typically overwriting or rearranging its input.

Auxiliary space: Memory used by an algorithm beyond the space occupied by its input. In-place status is judged by how auxiliary space grows as input size increases.
Out-of-place algorithm: An algorithm that uses additional storage proportional to its input or produces results in separate storage. This contrasts with the small auxiliary-space requirement that defines in-place algorithms.
Heapsort: A comparison sorting algorithm that builds a heap and repeatedly removes its maximum or minimum. Heapsort sorts an array in place with constant auxiliary storage.
Big O notation: A notation describing an upper bound on how a quantity grows with input size. In-place claims commonly bound extra space asymptotically rather than count every temporary variable.
Array reversal: Reordering an array so its elements appear in reverse order. Swapping elements from opposite ends demonstrates in-place rearrangement with constant extra storage.
Merge sort: A comparison sorting algorithm that divides data into halves, sorts them, and merges the results. Its standard array implementation uses an auxiliary buffer proportional to the input size.
Quicksort: A comparison sorting algorithm that partitions elements around pivots and recursively sorts the partitions. Common implementations partition in place, though recursion uses stack space.
Recursion: A method of solving problems in which a procedure calls itself on smaller or related inputs. Recursive calls consume stack space, which can complicate an in-place classification.
XOR swap algorithm: A method for exchanging integer values using repeated bitwise exclusive OR operations. It illustrates a constant-space swap, though ordinary temporary variables are usually clearer.
Counting sort: A sorting algorithm that counts occurrences of keys and uses those counts to place output values. Its auxiliary arrays typically grow with the input size or key range.

Linked from 6 pages