chickadee » srfi-132 » list-merge!

list-merge! < lis₁ lis₂procedure

This procedure makes only a single, iterative, linear-time pass over its argument lists, using set-cdr!s to rearrange the cells of the lists into the list that is returned--it works "in place." Hence, any cons cell appearing in the result must have originally appeared in an input. It returns the sorted input.

Additionally, list-merge! is iterative, not recursive--it can operate on arguments of arbitrary size without requiring an unbounded amount of stack space. The intent of this iterative-algorithm commitment is to allow the programmer to be sure that if, for example, list-merge! is asked to merge two ten-million-element lists, the operation will complete without performing some extremely (possibly twenty-million) deep recursion.

This procedure is equivalent to the SRFI 95 merge! procedure when applied to lists, except that it does not accept a key procedure.