Summary

• we proved that n log n is a lower bound for sorting algorithms that rely on comparisons

• Heapsort and Mergesort are two optimal algorithms considering this approach

• However, every algorithms has its drawbacks despite being „optimal“.