A Variant of the Fisher-Morris Garbage Compaction Algorithm

The garbage compactification algorithm described works in linear time and, for the most part, does not require any work space. It combines marking and compactification into a two-step algorithm. The first step marks all non-garbage cells and, at the same time, rearranges the pointers such that the cells can be moved, the second step performs the actual compatification.