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

  • 1
    $\begingroup$ 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 $\endgroup$ Feb 19 '14 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.