Sorting Algorithms

Types

• Merge Sort
• Quick Sort

Lower Bounds for Sorting Algorithms

Consider any sorting algorithm that operates by comparing elements in the input array. The algorithm can be thought of as a comparison (or decision) tree. The depth of the binary tree gives us the max number of comparisons that could be required to sort. The number of possible orderings is the number of leaf nodes in the tree $n!$.

If there are $n!$ permutations, a correct sorting algorithms needs to distinguish all permutations so $\text{number of leaves }\ge n!$.

A binary tree of depth $k$ has at most $2^{k+1}-1$ total nodes in the tree and at most $2^k$ leaves. To fit all permutations, $2^{k+1}-1\ge n!$. By lower bounding $\log (!n)$, and doing log math we can prove that any comparison-based sorting algorithm has a worst-case depth of $O(n\log n)$.