A comparison-based sorting of n numbers needs a minimum of roughly n log n operations. This paper presents a new derivation for this famous computer science fact. While, for the worst case, a straightforward proof utilizes ubiquitous binary trees, for the average case multivariable calculus is used. Since this topic is no longer a standard part of undergraduate computer science courses, the authors consider it worthwhile to introduce a proof without relying on advanced calculus.
In the spirit of discrete mathematics, the given proof employs Kraft’s inequality for the path lengths in a binary tree. Another tool is the Jensen inequality: the value of a convex function at a weighted linear combination of points is bounded by the same combination of the function values at these points. Highlighting different mathematical techniques, this treatment can definitely supplement academic programs.
Furthermore, it is instructional to expound lower bounds from the information-theoretical standpoint. Consider a reversal of a sorting algorithm, which produces input permutations from the ordered output. Apparently, with X comparisons, the variety of binary answers, 2X , cannot be less than the variety of all possible permutations, n. Using Stirling’s approximation and taking logarithms yields the desired result: X = O(n log n).
