Kodaj, B.; Móri, T. F. On the number of comparisons in Hoare’s algorithm “FIND”. (English) Zbl 0910.60002 Stud. Sci. Math. Hung. 33, No. 1-3, 185-207 (1997). Summary: In 1961 Hoare gave an extremely simple algorithm for finding the median from a list of size \(n\). That algorithm was later investigated by Knuth, who derived a closed form expression for the expected number of comparisons. In the present paper we show that the (random) number of comparisons, divided by \(n\), has a limit distribution as \(n\to\infty\), and the rate of convergence measured in Wasserstein metric is \(\Theta(\log n/n)\), while using other probabilistic distances, such as \(\Phi\)-average compound distances with convex Young functions \(\Phi\), the rate of convergence is \(\Theta(1/n)\). Cited in 3 Documents MSC: 60F05 Central limit and other weak theorems 68P10 Searching and sorting Keywords:median; coupling; Wasserstein metric; probability distances; Young functions; limit distribution; rate of convergence PDFBibTeX XMLCite \textit{B. Kodaj} and \textit{T. F. Móri}, Stud. Sci. Math. Hung. 33, No. 1--3, 185--207 (1997; Zbl 0910.60002)