A lower limit on comparison based sorting.
Objectives
We would like to :- Establish a lower bound on comparison based sorting.
Notes
- This is from CLRS.
- A decision tree is the binary tree that represents the "decisions" that must be made to reach a conclusion.
- In a decision tree, the leaves are "conclusions"
- The inner nodes are the decisions required to reach those conclusions.
- The tree is binary, because the questions are all yes-no.
Consider [a b c] where a, b and c are arbitrary values. What would merge sort do? All left side branches are true, all right side branches are false. () are sublists not yet merged. [] is the final list Since there are 3 elements, there are 3! = 6 leaves So h ≥ 3 a<b / \ (a,b)(c) / \ (b,a)(c) / \ a<c c<b / \ / \ [a](b)(c) / cab cba \ [b](a)(c) / \ b<c a<c /\ /\ / \ / \ abc acb bac bca
- It is reasonable to model comparison based sorting with a decision tree.
- Inner nodes are the comparisons
- The leaves are a permutation of the data that is in order.
- To simplify the math a bit, we will assume that no two data elements are the same
- This is to make each permutation unique.
- We know that for a set of n elements, there are n! permutations.
- Or, in other words, there are n! different ways to "sort" a set of unique elements.
- But only one is "correct".
- (Because we don't allow duplicate elements)
- So for a comparison based sort of n elements , a decision tree must support n! leaves.
- Therefore the height of the decision tree must be at least height h such that n! ≤ 2h.
- or log2n! ≤ h
- But we want to know this in terms of n, not h.
- Sterling's approximation gives us the relationship
- $n! \approx \sqrt{2\pi n} \frac{n^n}{e^n}$
- n! ≈ (2πn)1/2 nne-n
- log2n! ≈ log2(2π n)1/2 nne-n
- log(ab) = log(a) + log(b)
- log2n! ≈ log2(2πn)1/2 + log2 nn - log2e-n
- loga(bc) = c loga(b)
- log2n! ≈ 1/2 log2(2πn) + log2 nn - log2e-n
- log2n! ≈ 1/2(log22π + log2n) + log2nn - log2e-n
- But 1/2 log22π is constant.
- And 1/2 log2n is O(log2n)
- log2nn = n log2n = O(n log2n)
- log2e-n = -n log2e = O(n)
- Or log2n! ≈ O(n log2 n )
- So O(n log2n) ≤ h, the height of the tree.
- Remember, the tree must have n! leaves, or select 2h, st n! ≤ 2h
- So log2n! ≤ h
- Thus there must be at least O(n log2 n) comparisons in any decision tree that finds the correct permutation.
- And the best ANY comparison based sort can be is O(n log2n)
- NOTE, this is a lower bound on worst case.
- We could build a decision tree that has a better lower bound for some cases, but some would be much more than this.
- And we can build sorts where everything is much worse than this.