>>328
(5) は比較ソートに限った話なら決定木を使った説明などを見ますが。
出題ミスでないとすると、比較ソート以外も視野に入れて議論しろということなのかな・・？
わざわざ比較ソートでないソートの話で前振りしているところからして、
たぶんミスではないのでしょうね。

比較ソート以外のソート（数え上げソート、基数ソート 等）は、
キーの値について何らかの制約をかけることによって
n log n を下回る時間で動くというのが普通の話です。
しかし、キーに関して大小比較ができるということ以外に何の制約もかけないとしての
最悪計算量の下界なら、 Ω( n log n ) になるという話にもっていけるのかも知れません。

なんとなく、情報量の概念と関係が深い問題のように思います。