Lucky Cars and the Quicksort Algorithm
Pamela E. Harris, Jan Kretschmann, J. Carlos Martínez Mori · American Mathematical Monthly · 2024
Quicksort is a classical divide-and-conquer sorting algorithm. It is a comparison sort that makes an average of 2(n+1)Hn−4n comparisons on an array of size n ordered uniformly at random, where Hn:=∑i=1n1i is the nth harmonic number. Therefore it makes n![2(n+1)Hn−4n] comparisons to sort all possible orderings of the array. In this article, we prove that this count also enumerates the parking preference lists of n cars parking on a one-way street with n parking spots resulting in exactly n−1 lucky cars (i.e., cars that park in their preferred spot). For n≥2, both counts satisfy the second order recurrence relation fn=2nfn−1−n(n−1)fn−2+2(n−1)! with f0=f1=0.