Merge Strategies: from Merge Sort to TimSort

Abstract : The introduction of TimSort as the standard algorithm for sorting in Java and Python questions the generally accepted idea that merge algorithms are not competitive for sorting in practice. In an at- tempt to better understand TimSort algorithm, we define a framework to study the merging cost of sorting algorithms that relies on merges of monotonic subsequences of the input. We design a simpler yet competi- tive algorithm in the spirit of TimSort based on the same kind of ideas. As a benefit, our framework allows to establish the announced running time of TimSort, that is, O(n log n).
Type de document :
Pré-publication, Document de travail
2015
Liste complète des métadonnées

Littérature citée [4 références]  Voir  Masquer  Télécharger

https://hal-upec-upem.archives-ouvertes.fr/hal-01212839
Contributeur : Carine Pivoteau <>
Soumis le : mercredi 9 décembre 2015 - 15:12:32
Dernière modification le : jeudi 5 juillet 2018 - 14:45:56
Document(s) archivé(s) le : samedi 29 avril 2017 - 08:36:28

Fichier

merge_strategies.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01212839, version 2

Citation

Nicolas Auger, Cyril Nicaud, Carine Pivoteau. Merge Strategies: from Merge Sort to TimSort. 2015. 〈hal-01212839v2〉

Partager

Métriques

Consultations de la notice

2638

Téléchargements de fichiers

2350