یه درخت تصمیم گیری برای مرتب سازی بر اساس مقایسه لازم داریم. این درخت یه درخت دودوییه [tex]binary\: tree[/tex]

هر گره داخلی این درخت یه مقایسه بین دو عنصر رو نشون میده. هر برگ یه نتیجه مرتب شده رو نشون میده.
بخاطر [tex]n![/tex] چینش [tex]n[/tex] عنصر پس درخت ما حداکثر [tex]n![/tex] برگ داره. این درخت حداکثر [tex]2n!-1[/tex] گره داره.

پس عمق این درخت حداقل [tex]\log(n!)[/tex] هست.
رابطه [tex]n!\ge(\frac{n}{2})^{(\frac{n}{2})}[/tex] یه رابطه صحیحه. پس [tex]\log n!\ge\log(\frac{n}{2})^{(\frac{n}{2})}[/tex]

در نتیجه : عمق درخت از مرتبه [tex]O(n\: \log\: n)[/tex] هست. البته در حالت متوسط.