We introduce a novel approach to the classical problem of in-place, stable merging. Shufflemerge reduces the merging problem to the problem of realizing the ``perfect shuffle'' permutation, that is, the exact interleaving of two, equal length lists. The algorithm is recursive, using a logarithmic number of variables, and so does not use absolutely minimal storage.
A simple method of realising the perfect shuffle uses one extra bit per element, and so is not strictly in-place. We show that the perfect shuffle can be attained strictly in-place and in linear time, at the expense of doubling the number of moves, relative to the simple method.
Linear time, in-place, stable merging has previously been demonstrated. We present experimental evidence indicating that Shufflemerge, although almost certainly not asymptotically linear, could be of value in practice.
We note that there is a worst case requiring time Omega(n log n). We also present an analysis of a variant of Shufflemerge which uses a generalised shuffle and which has a provable average case time complexity of O(n log log n). The generalised shuffle is not likely to be realisable in-place.
The relative simplicity of the basic method, particularly with respect to stability also recommends it.