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. (c) 2005 Elsevier Inc. All rights reserved.

Efficient Unbalanced Merge-Sort

PROIETTI, GUIDO
2006-01-01

Abstract

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. (c) 2005 Elsevier Inc. All rights reserved.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11697/21408
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 4
social impact