# Hardness of optimal sorting

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')

• Knuth showed you could verify a comparison sort network by checking all 01 sequences, $O(2^n)$. Ian Parberry showed verification of sorting networks is co-NP complete, larc.unt.edu/ian/pubs/snverify.pdf Feb 19, 2014 at 16:54