Are there compare-based sorting algorithms that are faster than n lg(n) by some constant factor?

Question

Is it possible to have algorithms that sort using, say, $1/2 * N*lg(N)$ compares?

Essentially, I am confused because I have seen the $N * lg(N)$ lower bound on sorting written in both tilde and big-Omega notation.

Thanks.

Answer 1

The complexity notation is defined only up to a constant factor. AFAIK the constant factor is almost never used in analytic complexity analysis. Most of modern sorting algorithms have complexity $K * N * \log N$ where $K$ is some constant number. This number is typically hard to compute analytically, so empirical approaches are used instead. More precisely, the complexity of $N \log N$ is only an approximation for a general case. Many algorithms (e.g. quick sort) have special cases where they perform significantly worse than average. So in reality $K$ is not really a constant, but effectively a constant as long as the data stays in a certain regime. In practice, people select data regime (e.g. random data, or almost sorted data, or reverse-sorted data), and evaluate performance empirically using multiple runs. From such runs, you can fit the curve and get approximate values for $K$ for each algorithm, and thus conclude that some algorithms are better than others. But, in general, there is no one constant for an algorithm. All state of the art sorting algorithms target very specific data regimes and perform significantly worse if not used for the right job