Some Theorems on Sorting

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 ₂ 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.