问题的具体情况如下：有n个元素具有主键和辅助键，并且有m个辅助键。我们可以假设键是正整数，并且我们希望首先按主键对元素进行排序，然后按辅助键对元素进行排序。
我想知道是否有一个在 O(mlog n) 或 O(nlog m) 中运行的解决方案，理想情况下该解决方案应该使用通过 AVL 实现的堆，或者直接使用 AVL （如果您可以使用数组找出具有所需复杂性的解决方案，我也会接受它）。我要求特定的复杂性，因为简单的解决方案将首先按辅助键排序，然后对主键使用稳定的排序，如果两次使用合并排序，则运行时间为 O(nlog n) ，但是这并没有利用 m 比 n 小很多这一事实。