多次排序不同规模元素的增长阶：N次归并排序时间复杂度分析

• 单次归并排序的时间复杂度是O(k log k)，其中k为本次排序的元素规模。
• 循环执行N次时，总时间复杂度应为所有单次排序复杂度的总和，即O(Σ(M_i log M_i))，这里M_i代表第i次循环中待排序的元素规模。
• 你推导的O(nmlog(m))（m为平均规模）是一个宽松的上界，但并非总能准确反映实际复杂度：
  • 当所有M_i的规模都接近平均m时，这个近似是成立的；
  • 若各次M_i差异极大（比如某次规模远大于其他次），Σ(M_i log M_i)的增长速度会和nmlog(m)出现偏差。比如某次排序规模为2^n，其余均为1，总复杂度是O(n·2^n)，而用平均规模计算的nmlog(m)虽在大O层面量级一致，但无法体现实际的紧界。
• 更准确的表述应该是基于各次规模的累加和，而非直接用平均规模替代。

内容的提问来源于stack exchange，提问作者Lost Crotchet