lambda1@tg says to YSITD by some simplification you get on its worst input, it needs to perform Omega(n log n) comparisons