ECCC-Report TR20-096https://eccc.weizmann.ac.il/report/2020/096Comments and Revisions published for TR20-096en-usWed, 24 Jun 2020 20:41:11 +0300
Paper TR20-096
| On the asymptotic complexity of sorting |
Igor Sergeev
https://eccc.weizmann.ac.il/report/2020/096We investigate the number of pairwise comparisons sufficient to sort $n$ elements chosen from a linearly ordered set. This number is shown to be $\log_2(n!) + o(n)$ thus improving over the previously known upper bounds of the form $\log_2(n!) + \Theta(n)$. The new bound is achieved by the proposed group insertion sorting algorithm. Wed, 24 Jun 2020 20:41:11 +0300https://eccc.weizmann.ac.il/report/2020/096