Some Theorems on Sorting
Robert Morris · SIAM Journal on Applied Mathematics · 1969
It is a “well-known fact” that a lower bound for the average number of comparisons required to sort a table of N items is $\log _2 N!$, where the average is taken over all possible permutations of the table. In this paper a somewhat better lower bound is obtained, which in a way provides considerable insight into the theoretical limitations on methods of sorting by comparison.