Sorting Bounds, Non-Comparison Sorting & Binary Heaps

In a comparison sort, we only gain information about the input sequence (a_1, a_2, ..., a_n) by pairwise comparisons a_i <= a_j.

A decision tree models the execution of any comparison sort on n inputs:

- Each internal node represents a comparison a_i : a_j.

- Each leaf represents a unique permutation of the input elements.

Since any of the n! permutations could be the correct sorted order, the tree must contain at least n! reachable leaves (L >= n!).

A binary tree of height h has at most 2^h leaves. Therefore:

2^h >= L >= n! implies h >= log_2(n!)

Using Stirling's approximation (n! >= (n/e)^n):

h >= log_2((n / e)^n) = n log_2 n - n log_2 e = Omega(n log n).

Hence, any comparison sort requires at least Omega(n log n) comparisons in the worst case.

A common misconception is that building a heap of n elements takes O(n log n) because each Max-Heapify call takes O(log n) on n/2 nodes.

The key insight is that most nodes in a heap are close to the leaves and have very small heights h:

- An n-element heap has height lfloor log_2 n rfloor.

- At height h, there are at most lceil n / 2^{h+1} rceil nodes.

- Calling Max-Heapify on a node of height h takes O(h) time.

Total time to build the heap:

T(n) <= sum_{h=0}^{lfloor log_2 n rfloor} lceil frac{n}{2^{h+1}} rceil O(h) <= c n * sum_{h=0}^infty frac{h}{2^h}

Evaluating the infinite series S = sum_{h=0}^infty frac{h}{2^h}:

S = 1/2 + 2/4 + 3/8 + 4/16 + ...

S/2 = 1/4 + 2/8 + 3/16 + ...

S - S/2 = S/2 = 1/2 + 1/4 + 1/8 + ... = 1 implies S = 2.

Therefore: T(n) <= c n (2) = O(n). Building a binary heap takes strictly linear time!