Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR20-096 | 22nd June 2020 15:49

On the asymptotic complexity of sorting

RSS-Feed




TR20-096
Authors: Igor Sergeev
Publication: 24th June 2020 20:41
Downloads: 804
Keywords: 


Abstract:

We 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.



ISSN 1433-8092 | Imprint