The quicksort process (Q2434753): Difference between revisions

The authors investigate in detail ``quicksort on the fly'' using tools of higher mathematics. Given the input of \(n\) distinct numbers, the quicksort on the fly returns first the smallest, then the second smallest, and so on at the time of identification. Special attention is paid to analyzing the running time up to returning the \(l\)-th smallest out of \(n\) numbers. The output is a process in \(l\) converging ``weakly to a limiting process with path in the space of cadlag functions''. All the theoretical results are proved.