DROPS

Document

DOI: 10.4230/LIPIcs.AofA.2026.22

A Distributional Analysis of QuickXsort for Mergesort

Authors: Jasper Ischebeck, Florian Lesny, and Ralph Neininger

Published in: LIPIcs, Volume 381, 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)

Abstract

QuickXsort is an efficient in situ sequential sorting algorithm that mixes Hoare’s Quicksort algorithm with another sorting algorithm X, such as Heapsort, Insertionsort or Mergesort. The advantage is that QuickXsort can be in-place even if X is not. QuickXsort works recursively like Quicksort but uses sorting algorithm X on one of the sub-lists generated in each step. While the expected complexity of QuickXsort, measured by the number of key comparisons, has been investigated for various choices of X, here the asymptotic variance and distribution of the normalized complexity are studied with Mergesort used as X. Various versions of Mergesort and splitting regimes for the decomposition of the list by Quicksort are considered and periodicities in moments and the distributions are characterized.

Cite as

Jasper Ischebeck, Florian Lesny, and Ralph Neininger. A Distributional Analysis of QuickXsort for Mergesort. In 37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 381, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ischebeck_et_al:LIPIcs.AofA.2026.22,
  author =	{Ischebeck, Jasper and Lesny, Florian and Neininger, Ralph},
  title =	{{A Distributional Analysis of QuickXsort for Mergesort}},
  booktitle =	{37th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2026)},
  pages =	{22:1--22:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-435-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{381},
  editor =	{Panagiotou, Konstantinos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2026.22},
  URN =		{urn:nbn:de:0030-drops-262932},
  doi =		{10.4230/LIPIcs.AofA.2026.22},
  annote =	{Keywords: QuickXsort, Analysis of Algorithms, Mergesort, distribution analysis, limit law, weak convergence, contraction method}
}

Search Results

Documents authored by Lesny, Florian

A Distributional Analysis of QuickXsort for Mergesort

Abstract

Cite as

Thanks for your feedback!

Could not send message