Cited By
View all- Ghasemi EJugé VKhalighinejad GYazdanyar H(2024)Galloping in Fast-Growth Natural Merge SortsAlgorithmica10.1007/s00453-024-01285-6Online publication date: 9-Dec-2024
Adaptive Shivers Sort: An Alternative Sorting Algorithm
Article No.: 31, Pages 1 - 55
Abstract
We present a new sorting algorithm, called adaptive ShiversSort, that exploits the existence of monotonic runs for sorting efficiently partially sorted data. This algorithm is a variant of the well-known algorithm TimSort, which is the sorting algorithm used in standard libraries of programming languages, such as Python or Java (for non-primitive types). More precisely, adaptive ShiversSort is a so-called \(k\)-aware merge-sort algorithm, a class that captures ‘TimSort-like’ algorithms and that was introduced by Buss and Knop.
In this article, we prove that, although adaptive ShiversSort is simple to implement and differs only slightly from TimSort, its computational cost, in number of comparisons performed, is optimal within the class of natural merge-sort algorithms, up to a small additive linear term. This makes adaptive ShiversSort the first \(k\)-aware algorithm to benefit from this property, which is also a 33% improvement over TimSort's worst-case. This suggests that adaptive ShiversSort could be a strong contender for being used instead of TimSort.
Then, we investigate the optimality of \(k\)-aware algorithms. We give lower and upper bounds on the best approximation factors of such algorithms, compared to optimal stable natural merge-sort algorithms. In particular, we design generalisations of adaptive ShiversSort whose computational costs are optimal up to arbitrarily small multiplicative factors.
References
[1]
Nicolas Auger, Vincent Jugé, Cyril Nicaud, and Carine Pivoteau. 2018. On the worst-case complexity of Timsort. In Proceedings of the 26th Annual European Symposium on Algorithms (ESA ’18). Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 4:1–4:13. Retrieved from https://arxiv.org/abs/1805.08612
[2]
Nicolas Auger, Cyril Nicaud, and Carine Pivoteau. 2015. Merge Strategies: From Merge Sort to Timsort. Research Report hal-01212839. HAL.
[3]
Jérémy Barbay and Gonzalo Navarro. 2013. On compressing permutations and adaptive sorting. Theoretical Computer Science, 513 (2013), 109–123.
[4]
Josh Bloch. 2021. Timsort Implementation in Java. Retrieved from https://github.com/openjdk/jdk/blob/3afeb2cb4861f95fd20c3c04f04be93b435527c0/src/java.base/share/classes/java/util/ComparableTimSort.java
[5]
Sam Buss and Alexander Knop. 2019. Strategies for stable merge sorting. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 1272–1290.
[6]
Stijn De Gouw, Jurriaan Rot, Frank de Boer, Richard Bubel, and Reiner Hähnle. 2015. OpenJDK's Java.utils.Collection.sort() is broken: The good, the bad and the worst case. In Proceedings of the International Conference on Computer Aided Verification. Springer, 273–289.
[7]
Edsger Dijkstra. 1982. Smoothsort, an alternative for sorting in situ. In Theoretical Foundations of Programming Methodology. Manfred Broy and Gunther Schmidt (Eds.), Springer, 3–17.
[8]
Vladmir Estivill-Castro and Derick Wood. 1992. A survey of adaptive sorting algorithms. ACM Computing Surveys 24, 4 (1992), 441–476.
[9]
Adriano Garsia and Michelle Wachs. 1977. A new algorithm for minimal binary search trees. SIAM Journal on Computing 6, 4 (1977), 622–642.
[10]
Herman Goldstine and John von Neumann. 1947. Planning and Coding of Problems for an Electronic Computing Instrument. Research Report, Institute for Advanced Study.
[11]
Mordecai Golin and Robert Sedgewick. 1993. Queue-mergesort. Information Processing Letters 48, 5 (1993), 253–259.
[12]
Tony Hoare. 1961. Algorithm 64: Quicksort. Communications of the ACM 4, 7 (1961), 321.
[13]
Te Hu and Alan Tucker. 1971. Optimal computer search trees and variable-length alphabetical codes. SIAM Journal on Applied Mathematics 21, 4 (1971), 514–532.
[14]
Vincent Jugé. 2020. Adaptive Shivers sort: An alternative sorting algorithm. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms. 1639–1654.
[15]
Donald Knuth. 1998. The Art of Computer Programming, Volume 3 (2nd ed.) Sorting and Searching. Addison Wesley Longman Publish. Co., Redwood City, CA.
[16]
Heikki Mannila. 1985. Measures of presortedness and optimal sorting algorithms. IEEE Transactions on Computers 34, 4 (1985), 318–325.
[17]
Alistair Moffat, Gary Eddy, and Ola Petersson. 1996. Splaysort: Fast, versatile, practical. Software: Practice and Experience 26, 7 (1996), 781–797.
[18]
J. Ian Munro and Sebastian Wild. 2018. Nearly-optimal mergesorts: Fast, practical sorting methods that optimally adapt to existing runs. In Proceedings of the 26th Annual European Symposium on Algorithms (ESA ’18). Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 63:1–63:15.
[19]
Tim Peters. 2021. Timsort Description . Retrieved from https://github.com/python/cpython/blob/e5c8ddb1714fb51ab1defa24352c98e0f01205dc/Objects/listsort.txt
[20]
Olin Shivers. 2002. A Simple and Efficient Natural Merge Sort. Technical Report. Georgia Institute of Technology.
[21]
Tadao Takaoka. 2009. Partial solution and entropy. In Proceedings of the Mathematical Foundations of Computer Science 2009. Springer, 700–711.
[22]
Guido van Rossum and 69 Other Contributors. 2021. Timsort Implementation in CPython . Retrieved from https://github.com/python/cpython/blob/e5c8ddb1714fb51ab1defa24352c98e0f01205dc/Objects/listobject.c
[23]
John Williams. 1964. Algorithm 232: Heapsort. Communications of the ACM 7, (1964) 347–348.
Index Terms
- Adaptive Shivers Sort: An Alternative Sorting Algorithm
Recommendations
Adaptive shivers sort: an alternative sorting algorithm
SODA '20: Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete AlgorithmsWe present a new sorting algorithm, called adaptive ShiversSort, that exploits the existence of monotonic runs for sorting efficiently partially sorted data. This algorithm is a variant of the well-known algorithm TimSort, which is the sorting algorithm ...
Relations between Average-Case and Worst-Case Complexity
The consequences of the worst-case assumption NP=P are very well understood. On the other hand, we only know a few consequences of the analogous average-case assumption “NP is easy on average.” In this paper we establish several new results on the worst-...
Building a new sort function for a C library
Up to now, the most efficient sort function for a C library was a variant of Hoare's Quicksort (qsort, for short), which was proposed by Bentley and Mcllroy in the early 1990s. Here we call this library function BM qsort. This paper introduces a library ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publication rights licensed to ACM. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 05 August 2024
Online AM: 22 May 2024
Accepted: 30 April 2024
Revised: 28 September 2021
Received: 23 June 2020
Published in TALG Volume 20, Issue 4
Check for updates
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 276Total Downloads
- Downloads (Last 12 months)276
- Downloads (Last 6 weeks)41
Reflects downloads up to 12 Dec 2024
Other Metrics
Citations
Cited By
View all- Ghasemi EJugé VKhalighinejad GYazdanyar H(2024)Galloping in Fast-Growth Natural Merge SortsAlgorithmica10.1007/s00453-024-01285-6Online publication date: 9-Dec-2024
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in