lambda1@tg says to YSITD The proof is simple: Consider a decision tree where each node represents a comparison and thus has two children (either a<b or b<=a). The leaves represent the sorted array (sequences).