Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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 attempt 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 propose an optimal strategy for lists and a 2-approximation for arrays. We compare them to the merging strategy of TimSort by designing a simpler yet competitive algorithm based on the same ideas. As a side benefit, our framework allows to establish the announced running time of TimSort, that is O(n log n).
Document type :
Preprints, Working Papers, ...
Complete list of metadata

https://hal-upec-upem.archives-ouvertes.fr/hal-01212839
Contributor : Carine Pivoteau Connect in order to contact the contributor
Submitted on : Wednesday, October 7, 2015 - 3:01:36 PM
Last modification on : Tuesday, October 19, 2021 - 11:26:21 AM
Long-term archiving on: : Friday, January 8, 2016 - 10:34:02 AM

File

aunipi2016-merge-sorts.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01212839, version 1

Citation

Nicolas Auger, Cyril Nicaud, Carine Pivoteau. Merge Strategies: from Merge Sort to TimSort. 2015. ⟨hal-01212839v1⟩

Share

Metrics

Record views

180

Files downloads

58