Lower bound for comparison based sorting algorithms
The problem of sorting can be viewed as following. Input: A sequence of n numbers <a1, a2, . . . , an>. Output: A permutation (reordering) <a'1, a'2, . . . , a'n> of the input sequence such that a'1 <= a'2 ..... <= a'n. A sorting algorithm is comparison based if it uses comparison