如何排序，在2列上对2D阵列进行排序的时间复杂度是多少

Question

我想对一个由2列组成的2D数组进行排序，先在第0列，然后在第1列。示例：

1 2
3 4
1 5
2 6

排序后看起来像

1 2
1 5
2 6
3 4

我知道一个简单的排序算法可以基于1列进行排序，但当先使用列0，然后使用列1时，应该采用什么方法？此外，我对这件事的时间复杂性更感兴趣。只会是O(nlogn(吗？或者O((nlogn(^2(这是指第0列中的所有值都相同，但排序仍然需要O(nlog恩(时间，然后再次对第二列进行排序需要O(nlogn(时间。还是我错了？

排序算法：合并排序

Answer 1

Merge Sort有两个主要步骤：

1. 递归排序半长度的子列表
2. 合并递归排序的子列表

现在，1D和2D阵列的过程是相同的，唯一改变的是阵列对象的比较。以下是整数排序时排序键的一个简单实现：

def max(a,b):
if a>b:
return -1
return 1

现在，考虑一对int的排序键：

def max(a,b):
if a[0]>b[0]:
return -1
if a[0]<b[0]:
return 1
if a[1]>b[1]:
return -1
return 1

在这里，我们不是只进行1次比较，而是在最坏的情况下进行3次比较。因此，在最坏的情况下，每次操作可能需要3倍以上的时间。总体复杂度仍将保持为O(c*nlog(n))，其中c是常数。这归结为简单的O(nlog(n))复杂性。