Lower limit for sorting algorithms based on comparison ​

How fast can we sort $n$ elements?

Until now, we covered some algorithms which base their decision on the comparisons between keys but we had no assumption regarding the input's nature.

So what is the inferior limit, when it comes to these algorithms?

• A quick and wrong answer would be that the best time would be $\mathrm{\Omega }(n)$, but this is wrong

1 - Decision Tree as a representation ​

Let us use a decision tree to represent the comparisons done by a comparison sorting algorithm, given a generic input:

We notice that:

1. Every internal node is labeled from $i\text{ to }j$, with $i,j\in 1,\dots ,n$
   • It means we need to compare $a_i$ and $a_j$
   • L-subtree, includes the following comparisons if $a_i\le a_j$;
   • R-subtree, includes the following comparisons if $a_i>a_j$;
2. Every leaf represents a permutation $<{\pi }_1,\dots ,p{i}_n>$
   • Such that $a{\pi }_1\le a{\pi }_2\le \dots \le a{\pi }_n$
     • A permutation such that every element is sorted by some criteria;

Given any comparison sorting algorithm, and some input of size $n$, we can construct a decision tree (binary tree Y/N) for each $n$, that models all possible permutations and comparisons:

• Given any comparison sorting algorithm we can build a tree for every $n$
  • Each tree maps all the possible execution paths
• The execution time $T(n)$, which equals the count of comparisons, is the length of a path in the tree
  • The worst execution time is given by the height of the tree $T_{worst}(n)=height(T)=h$

The inferior limit on the heights of all the decisions trees (where each permutation appears like a leaf) behaves like the inferior limit of the execution time of any comparison sorting algorithm

Since it is a binary tree, we can use its height to find out the number of permutations which are exactly the number of leaves in the tree!

2 - How many leaves $f()$ can a decision tree, like the one we just mentioned, have? ​

2.1 - $f(T)\ge n!$ ​

Every permutation must appear at least once, trivially

2.2 Lemma: a binary tree of height $h$ has at most $2^h$ leaves ​

Demonstration ​

Induction on $h$:

1. Base Case: $h=0$, a tree with just one node which is both root and leaf
   • $f(T)=f(h=0)=1$
2. Inductive Hypothesis: We assume this is true for any tree of height $k<h$
3. Inductive Step: We show it for $h$
   • Tree with one child
     • $f(T)$ is equal to $f(T_1)$ which has height $h-1$, $f(T)=f(T_1)$
     • Then, by Inductive Hypothesis, $f(T)=f(T_1)\le 2^{h-1}\le 2^h\Rightarrow f(T)$
   • Tree with both children
     • $f(T)=f(T_1)+f(T_2)$, the leaves of the tree $T$ equals the sum of its children's leaves
     • Let $h_1,h_2<h$ be the height of the children
     • Then, by Inductive Hypothesis,
       • $f(T_1)\le 2^{h_1}\wedge f(T_2)\le 2^{h_2}$
       • $f(T)=f(T_1)+f(T_2)\le 2^{h_1}+2^{h_2}\le 2\cdot 2^{max(h_1,h_2)}\le 2^h$
       • $2\cdot 2^{max(h_1,h_2)}=2^{1+max(h_1,h_2)}\Rightarrow h=1+max(h_1,h_2)$
       • $2^{1+max(h_1,h_2)}=2^h$
       • The property is demonstrated as $f(T)\le 2^h$

3: Theorem ​

Any comparison sorting algorithm requires $T_{worst}(n)=\mathrm{\Omega }(nlog(n))$ comparisons

Demonstration ​

We need to determine the height of a binary decision tree where each permutation appears as a leaf. Let us consider a decision tree with height $h$ and $l$ leaves which represents the sorting process of a comparison sorting algorithm given $n$ elements:

Stirling's approximation for $n!$ ​

If $n$ is sufficiently large, we can get the dominant term and substitute it with $n$

Corollary ​

Heapsort and Mergesort are asymptotically efficient comparison sorting algorithms.