m给定一个具有行和列的矩阵n，其中每个条目由一对(a,b)整数组成。没有一对在矩阵中出现两次。
我们现在想对这些对进行排序，这样对于同一行中的两个对(a,b)，(c,d)我们有该对位于当且仅当(a,b)的左侧，即如果该对根据其条目按字典顺序排列。此外，对于同一列中的两对，当且仅当。(c,d)((a < c) or (a=c and b < d))(a,b)(c,d)(a,b)(c,d)((b < d) or (b=d and a < c)
如果我们找到一个所有行和列都满足上述条件的位置，我们称之为稳定。
通过首先根据行条件对所有对进行排序，很容易获得稳定的放置，这需要O(mn log(mn))时间。然后将此列表拆分为 m 个部分p_1,...,p_m（现在每个部分包含 n 个元素，并且对于每个(a,b)in p_i，(c,d)in p_jit is (a,b) < (c,d) if i < j）。现在p_i根据列条件对每个部分进行排序，O(n log(n))每个部分，即O(mn log(n))所有部分。将已排序的部分p_i写入列i可提供稳定的位置。
现在考虑特殊情况m=n，N=n²。有了上面的论点，我们得到一个稳定的位置可以及时获得O(N log(N))，这给出了一个上限。现在这提出了一个问题：
这个问题的下限是多少？是O(N log(N))最优的吗？