12
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 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$
    – Chad Brewbaker
    Feb 19, 2014 at 16:54

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.