For comparison-based sorting algorithms, asymptotically optimal algorithms in worst-case $\Theta(n\log n)$ comparisons are well known. From a purely theoretical perspective, however, exactly optimal sorting algorithms (minimizing exactly the number of comparisons) are only known up to $n=16$ and for particular values of $n$, as detailed in Kuth's The Art of Computer Programming, vol3, § 5.3.1, or Peczarski's New Results in Minimum-Comparison Sorting; Algorithmica'04.
Are there hardness results on the complexity of optimal sorting? In particular the following two problems:
- given $n$, compute $S(n)$ the minimal number of comparisons necessary to sort $n$ numbers
- given an arbitrary set of $k$ comparisons already computed, find a next comparison that should be asked in an optimal sort
- same question, assuming the set of $k$ comparisons is not arbitrary but the result of running the first $k$ steps of an optimal algorithm.
(The last question being one possible formalization for: 'what is the complexity of computing an optimal sorting algorithm')