On the Worst-Case Complexity of TimSort

Authors Nicolas Auger, Vincent Jugé, Cyril Nicaud, Carine Pivoteau



PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.4.pdf
  • Filesize: 0.6 MB
  • 13 pages

Document Identifiers

Author Details

Nicolas Auger
  • Université Paris-Est, LIGM (UMR 8049), UPEM, F77454 Marne-la-Vallée, France
Vincent Jugé
  • Université Paris-Est, LIGM (UMR 8049), UPEM, F77454 Marne-la-Vallée, France
Cyril Nicaud
  • Université Paris-Est, LIGM (UMR 8049), UPEM, F77454 Marne-la-Vallée, France
Carine Pivoteau
  • Université Paris-Est, LIGM (UMR 8049), UPEM, F77454 Marne-la-Vallée, France

Cite AsGet BibTex

Nicolas Auger, Vincent Jugé, Cyril Nicaud, and Carine Pivoteau. On the Worst-Case Complexity of TimSort. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ESA.2018.4

Abstract

TimSort is an intriguing sorting algorithm designed in 2002 for Python, whose worst-case complexity was announced, but not proved until our recent preprint. In fact, there are two slightly different versions of TimSort that are currently implemented in Python and in Java respectively. We propose a pedagogical and insightful proof that the Python version runs in O(n log n). The approach we use in the analysis also applies to the Java version, although not without very involved technical details. As a byproduct of our study, we uncover a bug in the Java implementation that can cause the sorting method to fail during the execution. We also give a proof that Python's TimSort running time is in O(n + n log rho), where rho is the number of runs (i.e. maximal monotonic sequences), which is quite a natural parameter here and part of the explanation for the good behavior of TimSort on partially sorted inputs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Sorting and searching
Keywords
  • Sorting algorithms
  • Merge sorting algorithms
  • TimSort
  • Analysis of algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Nicolas Auger, Cyril Nicaud, and Carine Pivoteau. Merge strategies: From Merge Sort to TimSort. Research Report hal-01212839, hal, 2015. URL: https://hal-upec-upem.archives-ouvertes.fr/hal-01212839.
  2. Jérémy Barbay and Gonzalo Navarro. On compressing permutations and adaptive sorting. Theor. Comput. Sci., 513:109-123, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2013.10.019.
  3. Bernhard Beckert, Reiner Hähnle, and Peter H Schmitt. Verification of object-oriented software: The KeY approach. Springer-Verlag, 2007. Google Scholar
  4. Sam Buss and Alexander Knop. Strategies for stable merge sorting. Research Report abs/1801.04641, arXiv, 2018. URL: http://arxiv.org/abs/1801.04641.
  5. Stijn De Gouw, Jurriaan Rot, Frank S de Boer, Richard Bubel, and Reiner Hähnle. OpenJDK’s Java.utils.Collection.sort() is broken: The good, the bad and the worst case. In International Conference on Computer Aided Verification, pages 273-289. Springer, 2015. Google Scholar
  6. Donald E. Knuth. The Art of Computer Programming, Volume 3: (2nd Ed.) Sorting and Searching. Addison Wesley Longman Publish. Co., Redwood City, CA, USA, 1998. Google Scholar
  7. Heikki Mannila. Measures of presortedness and optimal sorting algorithms. IEEE Trans. Computers, 34(4):318-325, 1985. URL: http://dx.doi.org/10.1109/TC.1985.5009382.
  8. J. Ian Munro and Sebastian Wild. Nearly-optimal mergesorts: Fast, practical sorting methods that optimally adapt to existing runs. In Hannah Bast Yossi Azar and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms (ESA 2018), Leibniz International Proceedings in Informatics (LIPIcs), pages 63:1-63:15, 2018. Google Scholar
  9. Tim Peters. Timsort description, accessed june 2015. URL: http://svn.python.org/projects/python/trunk/Objects/listsort.txt.
  10. Tadao Takaoka. Partial solution and entropy. In Rastislav Královič and Damian Niwiński, editors, Mathematical Foundations of Computer Science 2009, pages 700-711, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail