### Exact L2-Distance from the Limit for QuickSort Key Comparisons (Extended Abstract)

*Patrick Bindjeme, James Allen Fill*

#### Abstract

Using a recursive approach, we obtain a simple exact expression for the L2-distance from the limit in the classical limit theorem of Régnier (1989) for the number of key comparisons required by QuickSort. A previous study by Fill and Janson (2002) using a similar approach found that the d2-distance is of order between n-1 logn and n-1/2, and another by Neininger and Ruschendorf (2002) found that the Zolotarev ζ3-distance is of exact order n-1 logn. Our expression reveals that the L2-distance is asymptotically equivalent to (2 n-1 lnn)1/2.

Full Text: PostScript PDF