The Quicksort process

Quicksort on the fly returns the input of n reals in increasing natural order during the sorting process. Correctly normalized the running time up to returning the l-th smallest out of n seen as a process in l converges weakly to a limiting process with path in the space of cadlag functions.

MoreLess

Year of publication:	2014
Authors:	Ragab, Mahmoud ; Roesler, Uwe
Published in:	Stochastic Processes and their Applications. - Elsevier, ISSN 0304-4149. - Vol. 124.2014, 2, p. 1036-1054
Publisher:	Elsevier
Subject:	Sorting \| Quicksort \| Divide and conquer algorithm \| Random algorithm \| Running time analysis \| Stochastic process \| Cadlag functions \| Asymptotics \| Skorodhod metric

More details

Type of publication:	Article
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10010730377