1
$\begingroup$

Is there a proven upper bound on the number of possible sorting algorithms that cannot be reduced to another sorting algorithm?

Sorting algorithms with "useless steps" wouldn't count because they can be reduced by removing the useless steps. I define a "useless step" as something that can be removed from the algorithm without affecting the result. I would consider a no-op or a wait to be a "useless step".

Wikipedia lists 44 sorting algorithms. https://en.wikipedia.org/wiki/Sorting_algorithm

My motivation for this question is pure curiosity.

$\endgroup$
3
  • 4
    $\begingroup$ I encourage you to edit your question to elaborate. What kind of reduction are you imagining? Normally, we consider polynomial-time reductions, but all polynomial-time sorting algorithms can be polynomially reduced to all others. It's not clear what your definition of "useless steps" is. What is the motivation for counting the number of such algorithms? $\endgroup$
    – D.W.
    Jul 11 at 6:12
  • $\begingroup$ I added a definition for "useless steps" and a motivation. Since "all polynomial-time sorting algorithms can be polynomially reduced to all others". then maybe I cannot define a filter for the type of reductions allowed. $\endgroup$ Jul 11 at 18:30
  • 2
    $\begingroup$ Another infinite family of algorithms: the $n$-th algorithm hard-codes some (or optimal) sorting strategy for inputs of length at most $n$. For larger inputs, the algorithm just runs whatever. $\endgroup$
    – Dmitry
    Jul 11 at 18:32

2 Answers 2

1
$\begingroup$

No. There are an infinite amount of sorting algorithms that are essentially distinct.

I sketch the argument below (using Yao's topological sort model).

Inputs: unordered lists

Outputs: sorted list

A sorting algorithm transforms each input (a topological sort over the discrete order) into an output (a topological sort over the linear order).

Consider any finite partial order P of size N between the discrete order and the linear order of size N. ("Between" in the refining order on partial orders).

A sorting algorithm can be created transforming topological sorts over the discrete order to topological sorts over P, which then are transformed by the algorithm to the sorted output.

For heapsort the partial order P is a binary tree that is the Hasse diagram of the underlying partial order created by the algorithm. Its topological sorts are heaps.

Clearly infinitely many different partial orders P can be chosen (where differences in structure can occur for larger input sizes N).

Each choice of P determines a new sorting algorithm. Hence infinitely many sorting algorithms (with distinct "intermediate" orders P) exist.

$\endgroup$
5
  • $\begingroup$ This point of view has a flaw: the length of the corresponding programs is prohibitive and depends on $n$. So in practice they cannot be used. $\endgroup$
    – user16034
    Jul 11 at 21:43
  • $\begingroup$ The answer addresses the original question. The practicality is not necessarily a consideration in a theoretical answer. Yours refines the question by including a practicality requirement, ie bounded length, in which case of course there are only finitely many cases. I agree that the optimum algorithms case is interesting. $\endgroup$
    – Michel
    Jul 12 at 9:16
  • $\begingroup$ It is not a flaw btw to not consider practicality. Turing computability results do not consider this extra condition. You can decide they are flawed, but they simply are not further fine tuned under bound considerations. Neil Jones produced a book on this topic. My answer addresses the stated question. $\endgroup$
    – Michel
    Jul 12 at 9:21
  • $\begingroup$ When the OP mentions the 44 algorithms he finds on Wikipedia, I bet he is thinking of practical things. Not about the $10^{3172}$ useless sequences you could generate (useless because of their length and the difficulty of generating them). In fact they should not be called algorithms but just programs. $\endgroup$
    – user16034
    Jul 12 at 9:37
  • $\begingroup$ Most Turing computable programs are not practical and we only consider a tiny fraction of that in practice. That does not mean practitioners are not interested in Turing's results. Your final answer of algorithms of bounded length being a finite collection is trivial and does not focus on sorting algorithms, ie provides no bound for this class. The earlier part is of interest, classifying by distinct decision trees per n, but adding up over all n still yields an infinite amount of programs overall. $\endgroup$
    – Michel
    Jul 12 at 9:47
1
$\begingroup$

An obvious upper bound for the number of programs to sort $n$ numbers is $\left(\dfrac{n(n-1)}2\right)!\,2^{(n(n-1)/2)}$, an astronomical number. This is simply established by considering that you can perform at most $\dfrac{n(n-1)}2$ distinct pairwise comparisons, in any order, and every comparison can have two outcomes. That makes a decision tree of depth $\dfrac{n(n-1)}2$.

Among these, many include useless steps resulting from the transitivity law (if $a<b$ and $b<c$ are known, it is useless to compare $a$ to $c$). In addition, many of these are structurally equivalent, i.e. they are identical to a renaming of the compared elements. The census of these algorithms is a terrible endeavor.

Also quite interesting are the efficient programs, i.e. requiring no more than $O(n\log n)$ comparisons, and even better, the minimum-comparisons algorithms (https://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list). This is still an open problem.


But for most of these sequences of comparisons, the corresponding program does not "compress" and is virtually as large as the decision tree. That makes them completely impractical.

So a more interesting question is about the number of programs of bounded length, independently of $n$, which deserve the name of algorithms. There is perforce a finite number of such algorithms, though for large lengths it can be huge. This is because there is a finite number of text strings of bounded length (and most of them are no sorting at all, not even valid programs).


Can you beat the length of this code ?

def sort(a, n):
    for i in range(n):
        for j in range(0, n - i - 1):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
    return a
$\endgroup$
7
  • 1
    $\begingroup$ Finally, the answer is: there is a finite number of sorting programs if you set a maximum length. $\endgroup$
    – user16034
    Jul 11 at 21:45
  • $\begingroup$ @greybeard: I obviously mean in the same language as the sample. For a given language, there is a minimum length. $\endgroup$
    – user16034
    Jul 12 at 6:45
  • $\begingroup$ @greybeard: then I don't understand your "Depends". $\endgroup$
    – user16034
    Jul 12 at 7:08
  • $\begingroup$ @greybeard: sorry, I still don't get your comment. What are "it" and "it" ? "Can you beat" must get a yes/no answer. $\endgroup$
    – user16034
    Jul 12 at 7:10
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$
    – greybeard
    Jul 12 at 7:11

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.