Lucky Cars and the Quicksort Algorithm

Abstract

Quicksort is a classical divide-and-conquer sorting algorithm. It is a comparison sort that makes an average of $2(n+1)H_n-4n$ comparisons on an array of size $n$ ordered uniformly at random, where $H_n={\sum }_{i=1}^n\frac{1}{i}$ is the $n$th harmonic number. Therefore, it makes $n!\left[2(n+1)H_n-4n\right]$ 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\ge 2$, both counts satisfy the second order recurrence relation $f_n=2n{f}_{n-1}-n(n-1)f_{n-2}+2(n-1)!$ with $f_0=f_1=0$.

8 pages, and 2 figures, to appear in The American Mathematical Monthly

Cited by in corpus (1)

• Permutation Invariant Parking Assortments