Lower Bound for Comparison Based Sorting Algorithms
Introduction
Sorting is an essential problem that shows up in many areas of computer science. To state precisely, the sorting problem takes an input array A with n distinct elements and outputs a permutation of A such that for all i and j (i < j), A’[i] < A’[j]:
Sorting algorithms (algorithms that solve the sorting problem) generally use comparison to sort an array, that is, the algorithm makes a comparison between some (or all) pairs of distinct elements in the array. Most of the sorting algorithms fall into this category, and example algorithms are Merge sort, Quicksort, Heapsort, Bubble sort, etc.
When we look at the running time of these algorithms, we see that Merge sort is Θ(n log n), Quicksort is Θ(n log n), Bubble sort is O(n²). It is certainly interesting to know what is the lower bound for sorting, as people have tried to make sorting algorithms faster and faster throughout history. Thus, in this article, we will be trying to find a lower bound for comparison-based sorting algorithms.
However, there are algorithms out there that do not use comparison, for instance, bucket sort, radix sort, and counting sort, and their running time is about O(n). These algorithms have an assumption about the input data. Bucket sort is useful when you can model your data as I-I-D samples (Independent and identically distributed random variables) from the uniform distribution on zero one; Counting sort is especially useful when the data is an integer array and the elements are small. We will exclude these algorithms as we want our algorithms to have zero assumptions about the data.
Theorem
Every “correct” comparison-based sorting algorithm that sorts an input array A with an arbitrary length n has a lower bound (in terms of running time) of Ω(n log n).
Proof
Let’s fix a comparison-based sorting algorithm and an array A with length n. Since we are using a comparison-based sorting algorithm, the algorithm doesn’t look at the values of A in relative order; instead, the algorithm compares the values of two elements in A. Hence, it would be easier if we think all the input arrays that contain the elements {1, 2, 3, …, n}. Again, the values of individual elements are not important. The algorithm only cares about the conditional A[i] < A[j] or A[i] > A[j]. So, there is no loss in thinking about an array that contains {1, 2, 3, …, n}. (Note that if we were using a non-comparison-based algorithm, it would be incorrect to use such array since the values of individual elements are important)
How many arrays can we have with the elements {1, 2, 3, …, n}? The answer is n!. N elements can show up in n! different orderings. This is because there are (n) choices for the first element, (n-1) choices for the second, (n-2) for the third, and so on.
We are now interested in the number of comparisons that the algorithm makes. So let’s define a variable k, which is the upper bound of the number of comparisons. That is, for all the inputs (each of the n! inputs), this algorithm makes no more than k comparisons. Now, since we have n! different inputs, the algorithm has to execute differently on each n! input. If we think about the comparisons and assume a set L with length k:
L contains either 0 or 1, depending on the comparison. Since we said that the upper bound of the number of comparisons is k, the length of set L is k. Each different input yields a different pattern of 1s and 0s in the set L. Thus, we can say that the number of different execution paths is the number of subsets of set L, that is, 2^k.
By the pigeonhole principle, if 2^k < n! , then 2^k will be our holes, n! will be the pigeons. At least 2 permutations of the set {1, 2, 3, …, n} are going to have the same execution path. However, since every permutation is distinct, none of them is going to produce the same comparison result. The algorithm that is fixed is definitely not correct and if it outputs the correct sorted version in one permutation, it will get the other one wrong. So, you can’t have a common execution of 2 distinct inputs.
We learned that 2^k must be greater than or equal to n! in the previous case by the pigeonhole principle. How does this help us? We are trying to lower bound k, the number of comparisons. We can find the lower bound with the steps:
By Stirling’s Approximation, we know that log n! = n log n − n + 1. Thus, we showed that k ≥ n log n − n + 1, also known as Ω(n log n). And that is the lower bound for a comparison-based deterministic sorting algorithm.