Theoretical Limitations of Comparison Sorting

Key Insight

Comparison sorts exclusively use comparisons between elements to gain order information about an input sequence, such as 'a[i] <= a[j]'. Other operations like inspecting element values or gaining order information by different means are not permitted. For analysis, it is assumed that all input elements are distinct, rendering comparisons of the form 'a[i] = a[j]' redundant and simplifying analysis to 'a[i] <= a[j]' comparisons.

The behavior of comparison sorts can be abstractly represented by a decision-tree model. This is a full binary tree where each internal node denotes a comparison (e.g., 'i:j'), and its branches represent the outcomes (left for 'a[i] <= a[j]', right for 'a[i] > a[j]'). Each leaf node corresponds to a unique permutation of the input elements, representing a sorted order. For a sorting algorithm to be correct, every one of the 'n!' possible permutations of 'n' elements must appear as a reachable leaf in its decision tree.

The height of a decision tree corresponds to the worst-case number of comparisons performed by the algorithm. For a decision tree of height 'h' with 'l' reachable leaves, the fundamental inequality 'n! <= l <= 2^h' holds. Taking logarithms on both sides yields 'h >= log(n!)', which simplifies to 'h = Omega(n log n)'. This mathematical proof establishes a worst-case lower bound of Omega(n log n) comparisons for any comparison sort algorithm, confirming that algorithms like heapsort and merge sort, with their O(n log n) running times, are asymptotically optimal comparison sorts.