Efficient unbalanced merge-sort

Sorting algorithms based on successive merging of ordered subsequences are widely used, due to their efficiency and to their intrinsically parallelizable structure. Among them, the merge-sort algorithm emerges indisputably as the most prominent method. In this paper we present a variant of merge-sort that proceeds through arbitrary merges between pairs of quasi-ordered subsequences, no matter which their size may be. We provide a detailed analysis, showing that a set of n elements can be sorted by performing at most n⌊logn⌋ key comparisons. Our method has the same optimal asymptotic time and space complexity as compared to previous known unbalanced merge-sort algorithms, but experimental results show that it behaves significantly better in practice.