Python中用array.sort()排序m行n列二维数组的时间复杂度是多少

首先明确前提：Python无内置二维数组类型，题目所指的二维数组通常为嵌套列表（由m个长度为n的子列表组成，顶层列表共m个元素，每个子列表对应一行）；题目提到的array.sort()是口误，实际对应Python内置列表的原地排序方法list.sort()。

基础算法背景 #

list.sort()底层采用Timsort排序算法，针对元素为基础类型（如整数、字符串）的一维列表，时间复杂度为：

• 最好情况（列表基本有序）：O(N)
• 平均/最坏情况：O(N log N)
  其中N为列表的元素个数。

直接对二维嵌套列表调用arr.sort()的复杂度 #

此时排序操作的对象是每一行（即顶层列表的元素），而非所有二维元素，复杂度结合行比较成本计算：

• Timsort针对m个顶层元素的比较次数量级为O(m log m)
• 单次比较两个长度为n的子列表的成本：
  • 平均场景（行元素随机分布）：大概率仅需比较1~2个元素即可分出大小，单次比较成本为O(1)
  • 最坏场景（所有行的前n-1个元素完全相同）：需遍历完整行才能分出大小，单次比较成本为O(n)

最终总时间复杂度：

• 平均情况：O(m log m)
• 最坏情况：O(n · m log m)

常见需求对应的其他复杂度 #

若实际需求为以下两类，复杂度需另行计算：

• 对每一行单独排序（m次对长度为n的子列表调用sort()）：总复杂度为O(m · n log n)
• 对二维数组的所有元素统一排序：需先将二维数组拉平为元素总数为m·n的一维列表再排序，总复杂度为O(mn log(mn))

内容的提问来源于stack exchange，提问作者Raveen rex