Search Results

Documents authored by Ghasemi, Elahe

Track A: Algorithms, Complexity and Games
Galloping in Fast-Growth Natural Merge Sorts

Authors: Elahe Ghasemi, Vincent Jugé, and Ghazal Khalighinejad

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

We study the impact of sub-array merging routines on merge-based sorting algorithms. More precisely, we focus on the galloping sub-routine that TimSort uses to merge monotonic (non-decreasing) sub-arrays, hereafter called runs, and on the impact on the number of element comparisons performed if one uses this sub-routine instead of a naive merging routine. The efficiency of TimSort and of similar sorting algorithms has often been explained by using the notion of runs and the associated run-length entropy. Here, we focus on the related notion of dual runs, which was introduced in the 1990s, and the associated dual run-length entropy. We prove, for this complexity measure, results that are similar to those already known when considering standard run-induced measures: in particular, TimSort requires only 𝒪(n + n log(σ)) element comparisons to sort arrays of length n with σ distinct values. In order to do so, we introduce new notions of fast- and middle-growth for natural merge sorts (i.e., algorithms based on merging runs). By using these notions, we prove that several merge sorting algorithms, provided that they use TimSort’s galloping sub-routine for merging runs, are as efficient as TimSort at sorting arrays with low run-induced or dual-run-induced complexities.

Cite as

Elahe Ghasemi, Vincent Jugé, and Ghazal Khalighinejad. Galloping in Fast-Growth Natural Merge Sorts. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 68:1-68:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

  author =	{Ghasemi, Elahe and Jug\'{e}, Vincent and Khalighinejad, Ghazal},
  title =	{{Galloping in Fast-Growth Natural Merge Sorts}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{68:1--68:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-164098},
  doi =		{10.4230/LIPIcs.ICALP.2022.68},
  annote =	{Keywords: Sorting algorithms, Merge sorting algorithms, Analysis of algorithms}
Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail