In-place merging via the perfect shuffle permutation.

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.

In-Situ, Stable Merging by way of the Perfect Shuffle,
John Ellis and Minko Markov

The Computer Journal, vol 43 (1), 2000, pp 40 - 53.