Is there an upper bound on the number of different sorting algorithms

Question

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.

Answer 1

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.

Answer 2

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