linsort - 6
Lin / Devi
Worst case no. of comparisons for a sorting algorithm is
Length of the longest path from root to any of the leaves in the decision tree for the algorithm.
Which is the height of its decision tree.
A lower bound on the running time of any comparison sort is given by
A lower bound on the heights of all decision trees in which each permutation appears as a reachable leaf.