Derivation of the
Sorting Lower-Bound
lA sorting algorithm effectively establishes which of n! permutations the data are originally in and through a series of comparisons and exchanges permutes the data to a fixed order.
lThis can be viewed as a tree with n! nodes, constructed with binary internal nodes for comparisons.