比較ソートによるソートの最小限の比較

Question

here私は、最小2^nの場合がnより大きい必要があるので、任意のタイプの比較ソートを使用してn個の要素をソートするために必要なlog（n！ （順列の数）。私はちょうどこの行を理解していない、どのように比較が2^tの場合につながることができます。例を3回比較すると、1> 2、3 < 5,6> 9となり、どのように8つのケースが得られますか？

Answer 1

tの比較結果は2^tになる場合がありますか？

コメントツリーに表示されているように、意思決定ツリーとして表示すると、コメントに表示されるようになります。あなたが見ることができるように

     (a < b) 
      (a < c)     (a < c) 
    (b < c)  (b < c)  (b < c)  (b < c) 
    1  2 3  4 5  6 7  8 

、二つのブランチ内の各比較結果：3つのアイテム、あなたが終わると

(a < b) 
true  false 

：

単一の比較では2例を提供します。ツリーには8つの可能なパスがあります。各リーフノードは結果を表します。