仅用栈实现高效排序：多栈能否达成O(n log(n))时间复杂度？

是的，仅使用多个栈完全可以实现时间复杂度为O(n log n)的排序，核心是借助分治思想，用栈模拟归并排序或快速排序的执行流程，以下是具体实现思路：

基于归并排序的多栈实现 #

• 拆分阶段：
  用栈存储待拆分的子序列（可以直接存元素，也可以存子序列在原数组中的索引范围）。每次将一个子序列拆分为两个长度相近的子序列，压入栈中等待处理，直到所有子序列都只剩单个元素（单个元素本身就是有序的）。这个阶段的总操作数是O(n log n)，因为每个元素会被拆分log n次。
• 归并阶段：
  从栈中取出两个相邻的有序子栈，用额外的临时栈来完成归并：反复比较两个子栈的栈顶元素，弹出较小的那个压入临时栈，直到其中一个子栈为空，再将另一个子栈的剩余元素全部压入临时栈，最后将临时栈的元素反转（或者调整压入顺序）得到合并后的有序子栈，再把这个子栈放回栈中继续归并，直到最终得到一个完整的有序栈。归并阶段的时间复杂度同样是O(n log n)，每个元素会参与log n次归并操作。

基于快速排序的多栈实现 #

用栈来模拟快速排序的递归过程，存储待排序的子序列范围：

• 每次从栈中取出一个待排序的子序列，选择一个基准元素，通过栈的push/pop操作将子序列划分为小于基准和大于基准的两个子栈；
• 把这两个子序列的范围压入栈中，继续处理，直到所有子序列都被排序完成。
  平均情况下，每次划分操作的时间复杂度是O(n)，总共需要log n层划分，因此总时间复杂度为O(n log n)。

关键注意点 #

• 所有操作仅依赖栈的三个基本操作：push（入栈）、pop（出栈）、peek（查看栈顶），不需要其他数据结构辅助；
• 这种多栈排序的复杂度达到了基于比较的排序算法的下界，是最优的基于比较的排序方案，比双栈排序的O(n²)效率提升明显。

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