DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2018.4

On the Worst-Case Complexity of TimSort

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

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{auger_et_al:LIPIcs.ESA.2018.4,
  author =	{Auger, Nicolas and Jug\'{e}, Vincent and Nicaud, Cyril and Pivoteau, Carine},
  title =	{{On the Worst-Case Complexity of TimSort}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{4:1--4:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.4},
  URN =		{urn:nbn:de:0030-drops-94678},
  doi =		{10.4230/LIPIcs.ESA.2018.4},
  annote =	{Keywords: Sorting algorithms, Merge sorting algorithms, TimSort, Analysis of algorithms}
}

Document

DOI: 10.4230/LIPIcs.STACS.2016.12

Good Predictions Are Worth a Few Comparisons

Authors: Nicolas Auger, Cyril Nicaud, and Carine Pivoteau

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract

Most modern processors are heavily parallelized and use predictors to guess the outcome of conditional branches, in order to avoid costly stalls in their pipelines. We propose predictor-friendly versions of two classical algorithms: exponentiation by squaring and binary search in a sorted array. These variants result in less mispredictions on average, at the cost of an increased number of operations. These theoretical results are supported by experimentations that show that our algorithms perform significantly better than the standard ones, for primitive data types.

Cite as

Nicolas Auger, Cyril Nicaud, and Carine Pivoteau. Good Predictions Are Worth a Few Comparisons. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{auger_et_al:LIPIcs.STACS.2016.12,
  author =	{Auger, Nicolas and Nicaud, Cyril and Pivoteau, Carine},
  title =	{{Good Predictions Are Worth a Few Comparisons}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.12},
  URN =		{urn:nbn:de:0030-drops-57135},
  doi =		{10.4230/LIPIcs.STACS.2016.12},
  annote =	{Keywords: branch misses, binary search, exponentiation by squaring, Markov chains}
}

Search Results

Documents authored by Auger, Nicolas

On the Worst-Case Complexity of TimSort

Abstract

Cite as

Good Predictions Are Worth a Few Comparisons

Abstract

Cite as

Thanks for your feedback!

Could not send message