3 ms·
It is a common complaint in discussions about sort algorithms that the case for sorting numbers is a degenerate case and 'real' cases involve at least pointer c
by hinkley 5y ago
It is a common complaint in discussions about sort algorithms that the case for sorting numbers is a degenerate case and 'real' cases involve at least pointer chasing, which can make the cost of compares to stop being constant time, or have a constant time that is greater than log(n) (or worse, n).
Sometimes locality of reference may increase the total number of comparisons but decrease the average cost considerably. For practical applications like databases, it's the runtime that matters, not the theory.