Relaxation possibilities of the lower bound worst case sorting algorithms without quantum computation

Question

The sorting algorithms (merge-sort, quicksort...) are tought to have an absolutely hard lower bound which can not be outperformed by computation alone and this bound is $n*log_{2}(n)$,

The reason for this bound is that those algorithms are using the division by two devide and conquer method and as such they generate a binary tree that begins at a root and from there on branches two times from each node until it reaches the bottom to produce exactly $n$ leaves at the bottom level.

Since it is a binary tree, it has exactly $log_{2}(n)$ levels from the root down to the leaves and as such it costs $log_{2}(n)$ "computational decisions" to generate the tree and $n$ decisions to walk over all leaves, so $n*log_{2}(n)$ looks absolutely valid at first.

I don't argue about the factor $n$ before the $log_{2}(n)$, what I argue about is, why is it everywhere such a strict advocating consensus about to always use $log_{2}(n)$ in computer science.

Imagine for example instead if I don't use the binary devide&conquer method, but if I adress the indices of the list which are prime numbers, using the values of those indices as representational values to compute the differences of the indices between the primes. The resulted tree structure from such an algorithm will have many more branches than two at most of the nodes and the generated tree size will be much much lower.

An computational approximation of an list with 1000000000 and the assumption of having 10 splits instead of two would result in 270 times less computational decisions when the $log_{10}(n)$ insead of the $log_{2}(n)$ would be used and I'm quite confident that this can be relaxed to an even much smaller tree in general, if I'm not oversimplifying it at least.

Answer 1

Fist of all the $\Omega(n \log n)$ lower bound only applies to comparison-based algorithms, that is only to algorithm that can only obtain information on the relative orders of two input elements by pairwise comparisons.

They do not have to be divide and conquer algorithms and they do not have to generate any tree. The lower bound simply follows from the fact that there are $n!$ possible permutations of the input elements and any correct algorithm must be able to output all of them (given the inverse permutation as its input). This means that the number of branches on the longest computation of the algorithm must be at least: $$ \log ( n! ) > \log (n/e)^n = n \log n - n \log e > n \log n - 1.44 n = \Omega(n \log n). $$

Also, even in the case of comparison based-algorithms, an absolute lower bound of $n \log n$ (without the constant hidden in the $\Omega(\cdot)$ notation, as you write in the question) on the number of comparisons cannot possibly exist since, when $n=2^k$, each element in Mergesort is compared at most $k-1$ times, showing that the total number of comparisons is at most $n(k-1) = n \log n - n$.

Your proposed algorithm is not clear to me but, in general, if you change the model of computation by allowing other operations to be performed in addition to comparisons then the $\Omega(n \log n)$ lower bound does not apply anymore.

For example, given any constant $c$, in the word-RAM model you can sort a collection of $n$ elements between $0$ and $n^c$ in linear time using Radix sort, as long as the chosen word size $w$ allows to write $n$ in a (constant number of) memory word(s), as it is usually the case (it is standard to assume $w=\Theta(\log n)$).