3 ms·
The Asymptotic Complexity of Sorting
- ColinWright 6y agoWe still study the number of comparisons for sorting in introductory CS, although other factors like locality of reference may be more important in practice. Common topics are the log_2(n!) comparison-tree lower bound and the nearly-matching log_2(n!)+O(n) merge sort upper bound. Better sorts were known but still with an O(n) error term. Now Sergeev has reduced the error term to o(n).