Beating the lower bound
- Understand and explain how we can beat $\Omega(n \lg n)$ lower bound in "linear-time sorting algorithms."
Earlier, we stated
A lower bound on a restricted (such as comparison-based) model of computation sets a precedent that can only be outperformed by an algorithm that somehow does something outside the model.
For a comparison-based algorithm, the restriction is that the only information about data is obtained by comparisons between elements. We may be able to beat the lower bound if we acquire more information about the elements
For example, it turns out if we know the range of the values to be sorted, we can perform sorting in linear time!
The sorting algorithms that are not based on comparisons draw on assumptions (information) concerning the data to be sorted. Therefore, these algorithms are not as general as comparison-based algorithms.