Lucky Cars and the Quicksort Algorithm.

Quicksort is a classical divide-and-conquer sorting algorithm. It is a comparison sort that makes an average of 2 (n + 1) H n − 4 n comparisons on an array of size n ordered uniformly at random, where H n : = ∑ i = 1 n 1 i is the nth harmonic number. Therefore it makes n ! [ 2 (n + 1) H n − 4 n ] 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 f n = 2 n f n − 1 − n (n − 1) f n − 2 + 2 (n − 1) ! with f 0 = f 1 = 0 . [ABSTRACT FROM AUTHOR]