对初始为完全降序的序列做升序排序的最优算法是什么？

结论 #

针对初始状态为完全降序的数组（例如5, 4, 3, 2, 1）升序排序的需求，归并排序（merge sort） 是比基础实现的快速排序更优的选择。

核心原因 #

• 时间复杂度表现更稳定
  归并排序的时间复杂度不受输入数据初始顺序影响，始终稳定为 O(nlogn)，完全逆序输入不会带来任何性能退化。
  常规未优化的快速排序通常默认选择数组首元素或尾元素作为基准值（pivot），在完全降序的输入场景下，每一轮分区操作都会将数组拆分为长度为1和长度为n-1的两个极度不平衡的子数组，直接导致时间复杂度退化到 O(n²)，性能远低于同数据规模下的归并排序。
• 空间开销差异可忽略
  归并排序本身需要 O(n) 的额外辅助空间完成归并操作，基础快排在最优场景下空间复杂度仅为 O(logn)，但在完全逆序的最差场景下，快排的递归调用栈深度会达到n，空间复杂度同样退化到 O(n)，二者的空间开销差异在此场景下可以忽略不计。

补充说明：如果是采用随机选取pivot、三数取中等优化策略的快速排序版本，在完全逆序场景下也能稳定达到 O(nlogn) 的平均时间复杂度，此时可根据业务需求选择：需要稳定排序（相同值元素相对位置不变）的场景优先选归并排序，追求更低平均空间开销的场景可以选择优化版快速排序。

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