考虑这样一个问题：
对于一个长度为 n 的数组 A，最少需要几次比较，才能令其有序？
为了简化问题，我们只考虑数组中不存在重复元素的情况，即不存在 a1=a2 ( a1 , a2 属于 A )。
我们知道，数组 A 中每两个元素之间存在大小关系，对于两个元素 a1 和 a2，要么 a1 > a2 ，要么 a1 < a2 。我们将每两个元素的关系放入一个数组 R，例如，对于 n=3 的数组 A， R = [ord(a1,a2), ord(a1,a3), ord(a2,a3)] 。显然， R 的长度为 2^n。我们发现，(A的排列 -> R的组成)是一个单射，也就是说对于 A 的每一种排列，都有唯一确定且独特的 R 与其对应。在这个例子中， R 能够覆盖 2^3 = 8 种不同的情况。也即
R1 = [>, >, >] R2 = [<, <, <]
R3 = [>, >, <] R4 = [<, <, >]
R5 = [>, <, >] R6 = [<, >, <]
R7 = [>, <, <] R8 = [<, >, >]然而我们可以发现，这八种情况实际上有两种是不可能发生的。例如， R5 和 R6 违反了序的传递性。实际上，这两种情况也正是 2^n 中除了 n! 以外的所有例外情况。显然，n! 就是 A 数组的全排列种类数。
所以，我们只需另 R 所能涵盖的组成数量大于 A 的全排列数，就能根据数组 A 中两两元素的大小关系来找到对应的 A 的排列。事实上，我们只需要 x=log2(n!) (上取整) 次比较即可确定 A 的排列。例如在上面的例子中 x=log2(3!)≈2.6=3 ， 令 |A| 为 A 的全排列种数，此时 |A|=6 ：在三次比较中，第一次比较得到 s1=ord(a1,a2) ，我们可以根据s1从 A 的所有排列中删去所有不满足 s1 的情况，剩下 |A|=3；接着第二次比较得到 s2=ord(a1,a3) ，我们可以从中得到两种情况，若 s1: >, s2: >，那么我们可以从剩下的 A 的排列中删去两个，得到 |A|=1 ，此时剩下的一种情况就是 A 的有序排列，其他情况以此类推。
如果我们在题目中允许重复元素的出现，那么当我们遇到重复元素的时候，如若 a1=a2 ，那么我们可以在后续的比较中直接将 a2 替换为 a1 ，即不用再考虑 a1 与其他元素的比较，因为我们可以直接将其等价于 a2 与其他所有元素的比较。那么此时我们只需要更少的比较数便能确定原数组的有序状态。然而在允许出现重复元素的数组中也可能不出现重复元素，在最差的情况下依旧需要 x=log2(n!) 次问询比较，因此对于允许有重复元素出现的数组，我们依旧需要 x=log2(n!) 次比较，才能确保能够得到其有序排列。