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⌋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.