linsort - 2
Lin / Devi
Only comparison of pairs of elements may be used to gain order information about a sequence.
Hence, a lower bound on the number of comparisons will be a lower bound on the complexity of any comparison-based sorting algorithm.
All our sorts have been comparison sorts
The best worst-case complexity so far is (n lg n) (merge sort and heapsort).
We prove a lower bound of n lg n, (or (n lg n)) for any comparison sort, implying that merge sort and heapsort are optimal.