Abstract In this paper we consider the problem of optimally merging two sets of ordered data such that the mean absolute distance (discrete l 1 norm) that a merged element must move in order to properly order the combined set is minimized. The final sorting algorithm then only needs to move the merged elements a short distance. Such a problem is important in the implementation of multidimensional order statistics and related filters and database applications. A powerful result obtained under the assumption that the elements of both sets are independent and identically distributed (iid) and are derived from the same continuous parent distribution is that the optimal merging (using any l p norm) is independent of the parent distribution. The exact solution to the minimization problem for the l 0+, l 2 and l ∞ cases are given and used as a basis for choosing a good approximation solution for the positions which minimize the l 1 norm. The performance for typical 2-D and 3-D filtering and database applications are also given.