  Using multisets, we develop novel techniques for mechanizing the proofs of
the synthesis conjectures for list-sorting algorithms, and we demonstrate them
in the Theorema system. We use the classical principle of extracting the
algorithm as a set of rewrite rules based on the witnesses found in the proof
of the synthesis conjecture produced from the specification of the desired
function (input and output conditions). The proofs are in natural style, using
standard rules, but most importantly domain specific inference rules and
strategies. In particular the use of multisets allows us to develop powerful
strategies for the synthesis of arbitrarily structured recursive algorithms by
general Noetherian induction, as well as for the automatic generation of the
specifications of all necessary auxiliary functions (insert, merge, split),
whose synthesis is performed using the same method.
