Zh. Vychisl. Mat. Mat. Fiz., 2021 Volume 61, Number 2, Pages 345–362
(Mi zvmmf11203)
|
Computer science
On the upper bound of the complexity of sorting
I. S. Sergeev Research Institute "Kvant", Moscow
Abstract:
It is shown that
$\log_2(n!)+o(n)$ pairwise comparisons is sufficient for sorting any subset of
$n$ elements of a linearly ordered set.
Key words:
sorting, complexity, decision tree, partial order, simplex.
UDC:
519
Received: 18.09.2019
Revised: 23.07.2020
Accepted: 16.09.2020
DOI:
10.31857/S0044466921020125
© , 2025
References