Comparison of Sorting Algorithms and the Lower Bound

• Elementary Sorting, Merge Sort, Quicksort, Heapsort and Linear-Time Sorting: the algorithms being compared.
• Trees and Binary Trees: a binary tree of height $h$ has at most $2^h$ leaves.

• each internal node is a comparison $a_i : a_j$, with one subtree for each outcome;
• each leaf is a permutation $\pi$, meaning "the sorted order is $a_{\pi(1)} \le a_{\pi(2)} \le \dots \le a_{\pi(n)}$";
• one execution follows one root-to-leaf path; its number of comparisons is the length of that path.

The lower bound

• Merge sort and heapsort, with $O(n \lg n)$ worst-case comparisons, are asymptotically optimal comparison sorts.
• The exact bound $\lceil \lg(n!) \rceil$ is 1 for $n = 2$, 3 for $n = 3$, 5 for $n = 4$, 7 for $n = 5$ and 10 for $n = 6$. For these small $n$ it is achieved, so it is the minimum worst-case number of comparisons. In general it is only a lower bound: no theorem says some algorithm meets it for every $n$.
• The best case is at least $n - 1$. Every leaf of a correct decision tree is at depth at least $n - 1$. Think of each comparison as an edge between two keys: if the edges seen on a path do not connect all $n$ keys, two of the resulting groups have never been compared, and the algorithm cannot know their relative order. Insertion sort on sorted input meets this with exactly $n - 1$ comparisons; in Figure 1 the shortest paths have length $2 = n - 1$.
• Nearly sorted input. For $1\le k\le n-1$, if every key is at most $k$ positions from its sorted place, a min-heap of the next at most $k+1$ keys sorts in $O(n\lg(k+1))$ time. For a lower bound, permute keys independently inside $q=\lfloor n/(k+1)\rfloor$ full blocks of $k+1$ consecutive sorted ranks, leaving the remaining keys fixed. All $((k+1)!)^q$ permutations satisfy the displacement limit, requiring at least $\lceil q\lg((k+1)!)\rceil$ worst-case comparisons, which is $\Omega(n\lg(k+1))$. For $k=0$, the input is already sorted; reading or outputting it takes $\Theta(n)$, and no comparison lower bound of that order is implied.
• Average case too. The average depth of the $n!$ leaves of any binary tree is at least $\lg(n!)$, so the average number of comparisons, over uniformly random orderings, is also $\Omega(n \lg n)$. Quicksort's $\Theta(n \lg n)$ average is therefore optimal in order.
• The bound applies only to comparison sorts. Counting, radix and bucket sort avoid it by using key values as indices.

• Stable sorts in the table. bubble, insertion, merge, counting, radix, bucket. Unstable: selection (array form), quicksort, heapsort. Any sort can be made stable by sorting pairs $(\text{key}, \text{original index})$, at the cost of extra space.
• In place. bubble, selection, insertion, heapsort, and quicksort (stack excepted). Merge sort on arrays and the three linear-time sorts are not.
• Already sorted input. insertion sort and flagged bubble sort take $\Theta(n)$; quicksort with a first or last pivot takes $\Theta(n^2)$; merge sort stays $\Theta(n \lg n)$; heapsort does too for distinct keys, but duplicate-heavy sorted inputs can be faster; selection sort stays $\Theta(n^2)$.
• All keys equal. insertion and bubble $\Theta(n)$; heapsort $\Theta(n)$; Lomuto quicksort $\Theta(n^2)$; three-way quicksort $\Theta(n)$.
• Lower bound statements. "every comparison sort takes $\Omega(n \lg n)$ time on some input" is true; "every comparison sort takes $\Omega(n \lg n)$ time on every input" is false (insertion sort on sorted input takes $\Theta(n)$).

• "Which sort" questions. match the stated constraint (stability, space, worst case, nearly sorted input) with the table above.
• Counting questions. minimum comparisons for max, min-and-max, second largest, merging, or sorting a few keys; use the exact formulas and check the parity of $n$.
• Lower-bound reasoning. decision tree height $\ge \lceil \lg(n!) \rceil$; every leaf depth $\ge n - 1$ (best case of any comparison sort); $\Omega(n \lg k)$ for inputs whose keys are within $k$ of their place; for partial problems, count the outcomes the algorithm must distinguish (for example, $\binom{2n}{n}$ possible interleavings when merging, giving at least $\lg \binom{2n}{n}$ comparisons).
• Traps. heapsort's best case on distinct keys is still $\Theta(n \lg n)$; quicksort is in place but not stable; merge sort is stable but not in place; the $\Omega(n \lg n)$ bound is a worst-case and average-case bound, not a best-case one.

• Elementary Sorting: prerequisite. Quadratic sorts and inversions.
• Merge Sort, Quicksort, Heapsort: prerequisites. The $n \lg n$ sorts.
• Linear-Time Sorting: related. Sorting without comparisons.
• Searching: related. The same decision-tree argument for search.
• Trees and Binary Trees: related. Leaves versus height in binary trees.