In-place

Also known as: In place algorithm, Constant extra space

An in-place algorithm transforms the input using only $O(1)$ (or at most $O(\log n)$ for recursion stacks, depending on the course definition) extra memory beyond the input storage.

Heapsort and typical quicksort partitions are in-place; classic merge sort is not. “In-place” is about space complexity, not about time.

Check the definition your exam uses: some allow the $O(\log n)$ call stack; others demand strictly constant auxiliary words.

← Back to CS Glossary