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

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

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

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