LAUSR

Abstract The algorithm Partial Quicksort, introduced by Conrado Martinez, sorts the l smallest real numbers for a set of n different ones. It uses a splitting like Quicksort, continuing always with the leftmost list. The normalized running time Y n ( t ) converges with l n → t in distribution to a non degenerate limit. The finite dimensional distributions of the process Y n converge to a limit (Ragab and Roesler (2014)), called the Quicksort process. In this paper we will present the algorithm Quicksort on the fly, a version of Partial Quicksort, showing the almost sure convergence of Y n to the Quicksort process in Skorokhod metric.