Optimal M-D sorting using distributions of order statistics

Consideration is given to the problem of optimally merging two sets of ordered data such that the mean absolute distance (discrete l₁ norm) that a merged element must move in order to properly order the combined set is minimized. Such a problem is important in the implementation of multidimensional order statistics filters and database applications. A powerful result obtained under the assumption that the elements of both sets are independent and identically distributed 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