给出以下二维数组：
6 8 11 17
9 11 14 20
18 20 23 29
24 26 29 35
每个行和列都被排序，对角线也被排序（从左上到右下）。假设我们在数组中有n²个元素（在这种情况下为n = 4），那么使用快速排序的琐事就很简单了，它需要O(n² log(n²)) = O(n² log(n))对2d数组进行排序。我的问题是我们可以在O(n²)中排序吗？
目标是使用给定的半排序2d数组并提出一个聪明的解决方案。
目标输出是：
6 8 9 11
11 14 17 18
20 20 23 24
26 29 29 35
是，我们可以在[[O（n ^ 2）时间里对它进行排序。
简化对一维数组的排序
让我们首先展示一下这个对2D数组排序的新问题（可以对每一行，每一列以及从左上到右下的对角线进行排序），可以简化为对< [n ^ 2元素。假设我们有一个n ^ 2个元素的排序一维数组。我们可以通过将第一个
n编号设置为第一行，然后将下一个n编号设置为第二行，来将其重新排列为排序的nxn数组，然后重复进行直到我们耗尽数组。
因此，给定2D数组n ^ 2个数字，我们可以在O（n ^ 2）
时间内将其转换为一维数组，对该数组进行排序，然后将其转换回所需的O（n ^ 2）时间的二维数组。因此，如果我们可以在O（n ^ 2）中找到一维数组的排序算法，则可以在O（n ^ 2）时间内等效地解决这个新问题。在线性时间内排序一维数组鉴于此，我们只需要提供线性时间排序即可。也就是说，给定n ^ 2
个元素，请在O（n ^ 2）
个时间对其进行排序。方便地，可以使用多种算法来完成此操作，例如counting sort或radix sort，尽管它们确实带有各种警告。但是，假定给定要排序的项目数，则在合理的数值范围内，这些排序将在线性时间内进行。因此给定nxn数组中的n ^ 2
个元素，此2D排序问题可以在O（n ^ 2）时间内减少为一维排序问题，然后可以在O（n ^ 2）时间内使用各种线性时间排序算法求解。因此，总的来说，这个问题可以在O（n ^ 2）时间内解决。按比较排序排序在评论中进行讨论之后，下一步是问：比较排序如何。比较排序是有益的，因为它可以避免前面提到的计数和基数排序的警告。但是，即使有了这些附加信息，在实践中也不太可能进行线性时间比较排序，因为这将要求我们计算 O（1）
让我们考虑一个小例子：最初在第1行第2列中的数字的最终排序位置应该是什么？我们知道它必须是第2 ... n列中的第一个数字。但是，我们不知道它相对于第1列中的数字属于什么位置（第1行第1列中的数字除外）。
通常，对于原始正方形中的任何数字，我们都不确定其相对于左下角的所有数字和右上角的数字的最终排序位置。需要进行[[O（log_2（n））比较才能找到每个数字的相对位置，并且还有O（n ^ 2）
个数字要定位。这种不确定性使我们无法在实践中实现线性时间排序。但是我们拥有的其他信息应该可以使我们加快速度。例如，我们可以使merge sort适应此问题。在标准合并排序中，我们首先将原始数组拆分为一半，然后重复进行，直到我们保证可以对大小为1的数组进行排序，然后我们重复合并这些子数组，直到只有一个数组。对于n ^ 2元素，我们必须创建一个具有log_2（n ^ 2）
层的二叉树，并且每一层需要O（n ^ 2）
的合并时间。使用问题设置中的附加信息，我们不必拆分数组，直到它们的大小为1。相反，我们可以从n长度为n的排序数组开始，然后开始从那里合并。这使我们必须合并的层数减半，并为我们提供了最终运行时间O（n ^ 2 log_2（n））
。结论实际上，此附加信息允许对比较排序进行某些加速，从而使我们能够实现O（n ^ 2 log_2（n））运行时间。
但是为了获得以O（n ^ 2）
时间运行的线性时间排序，我们必须依靠诸如计数或基数排序之类的算法。