大部分排序算法的过程可以用一棵树来表示。下图展示了排序$a1$、$a2$、$a3$三个数字的过程，每种排序情况最后都终止于一个叶子节点。如果假设在某一个分支上两元素相等也进入左子树的话，最终的排序树就是一棵二叉树。树的深度等同于从叶子节点到根节点的最长路径即为算法的最差情况复杂度，在这个例子中是3。
将这个例子推广到所有排序$n$个元素的排序算法，排序树的叶子都被所有可能的排序序列标识，换句话说每一种可能排序都对应一个叶子节点。$n$个元素有$n!$种可能的排序情况，也就是有$n!$个叶子节点。对于一棵深度为$d$的二叉树，最多有$2^d$个叶子节点。由$n!\leq 2d$推得$d\geq \log n!$，那么树的深度也即排序算法的复杂度最少为$\log(n!)$。
$n!=1\times2\times\cdots\times n$中至少有$\frac{n}{2}$个因子大于等于$\frac{n}{2}$，也即$n!\geq (n/2)^{(n/2)}$。对两边取对数就得到$\log (n!)\geq \frac{n}{2}\log(n/2)$
因此可以用上例中这种形式的排序二叉树表示排序过程的排序算法，算法复杂度的下限都为$\Omega(nlog2n)$。