非递归快速排序算法：显式栈模拟与栈深控制实践

1. 先搞清楚：为什么要把递归快排掰成非递归

写过无数次quickSort(arr, low, high)的人，第一次被问到“能不能不用递归实现”时，反应通常是愣一下——能是能，但图什么呢？我最早也是这个态度，直到有一次在一个数据量接近千万的离线排序任务里，程序半夜挂掉，日志只留下一行栈溢出。那一刻才真正理解，非递归版快速排序算法不是一个炫技的玩具，它的核心价值在于把“程序自己管理的调用栈”换成“我自己的堆内存数据结构”，从而把不可控的风险变成可控的、可以预算的资源。

具体来说，递归快排的问题不在算法本身，而在于调用栈是操作系统分配的、容量固定且通常很小。Linux 下主线程默认栈大小一般 8MB，一个快排的递归帧，编译器优化后少说也要几十字节，没优化时上百字节。数学期望上快排递归深度是 O(log n)，听起来很美好，但那是“平均情况”。一旦数据里有大量重复元素、或者输入已经基本有序而分区策略又选得不好，深度就会退化到 O(n)。n 是一百万时，一百万层乘以几十字节，妥妥几十兆，栈直接就崩了。而且崩溃现场往往离真正的问题很远，排查起来非常痛苦。

非递归版本解决的就是这件事。你用std::vector或者一个普通数组当栈，把它放在堆上，内存有多大、能撑多少层，自己心里有数；栈的深度还可以通过“先处理小区间、后压大区间”的技巧压到 O(log n)，最坏情况下也只是几十个元素的事情。除此之外，非递归版本在调试时还有个隐性好处：栈里的内容是你自己定义的结构，可以打印、可以断点、可以统计每一轮分区的区间大小，而系统调用栈在 release 模式下经常被优化得面目全非。

当然，我也得说清楚它不能带来什么。网上有些说法暗示非递归一定更快，这个结论站不住脚。函数调用本身在现代 CPU 上很便宜，压栈出栈也就几条指令，改成显式栈反而多了一次内存读写。实测下来两者在常规数据上性能基本持平，差距在 5% 以内，谁快谁慢取决于编译器和具体写法。所以如果你的目标只是“提速”，那应该去看分区策略和缓存友好性，而不是纠结递归还是迭代。

适合认真读下去的人大概是这几类：一是正在准备技术面试，被“非递归快排”这个经典问题卡住过的；二是在嵌入式、实时系统或者栈空间受限环境里写代码，必须自己掌控内存的；三是想彻底搞懂快排执行过程，而递归写法太“黑箱”看不透的。下面我会把设计思路、栈的用法、分区函数的坑、完整代码和实测数据一层层拆开，代码给 C++ 和 Python 两版，能直接抄。

2. 整体设计：用一个显式栈模拟递归的执行顺序

2.1 先把递归版本拆成“待办清单”

理解非递归最快的方式，是别把它当成另一套算法，而是当成对递归过程的一次手工展开。递归版快排的逻辑其实只有三步：对当前区间[lo, hi]做一次分区，得到基准位置p；然后递归处理[lo, p-1]；再递归处理[p+1, hi]。注意这里的关键点——分区的结果和两个子区间的处理顺序无关，先处理左边还是先处理右边，最终数组都是有序的。

这一步“顺序无关”的性质，就是整个转换的钥匙。既然顺序无关，那我完全可以不用“马上递归进去”的方式，而是把[lo, p-1]和[p+1, hi]这两个任务写在一张待办清单上，等手上的活儿干完了，再从清单里挑一个继续干。这个“清单”就是栈。递归版本里，这张清单是编译器帮你维护的（存在调用栈里）；非递归版本里，这张清单是你自己维护的（存在一个数组或 vector 里）。本质上没有任何算法上的变化，变的只是“谁来记这件事”。

所以整个算法的骨架就变成一句话循环：从栈里弹出一个区间，如果这个区间元素个数大于 1，就分区，然后把分出的两个子区间压回栈里；直到栈空为止。我第一次把这个逻辑写出来的时候有种恍然的感觉——原来递归的“回溯”不过是弹栈而已。

2.2 栈里到底存什么，这个选择比想象中重要

最直觉的做法是存一对下标(lo, hi)。C++ 里用std::pair<int,int>，Python 里直接塞元组。这样做的好处是代码干净，读起来和递归版的参数完全对应。但也有别的存法，比如只存lo和一个长度，或者把(lo, hi)打包进一个uint64_t（高低 32 位各存一个），后者在极端性能场景下能省一半内存和一次间接寻址。

我个人的建议是：除非你在做性能极限压榨，否则老老实实用 pair。理由很实在——打包成uint64_t的写法可读性极差，别人接手时要先反应三秒，而且一旦下标类型不是 32 位（比如你在处理超大数组需要 64 位下标），整个方案就得推翻重来。pair<int,int>一份 8 字节，栈的深度上界在 O(log n)，就算 n 是十亿，栈里也不会超过几十个元素，撑死几百字节，完全没必要为这点内存做优化。

另一个容易忽略的点是栈的容量预分配。C++ 的std::vector在 push 时如果容量不够会重新分配，虽然摊还成本是 O(1)，但在快排这种热点路径上，一次意外的 realloc 就可能带来几十微秒的抖动。我的习惯是一开始就reserve(64)，因为采用下面的“先小后大”策略后，栈深理论上不会超过 64 层，一次分配到位，后面全程零 realloc。

2.3 入栈顺序的坑：为什么必须“先压右、后压左”

这是个非常经典的细节。栈是后进先出，你压进去的顺序和弹出来的顺序是相反的。递归版里，如果你写的是“先递归左边，再递归右边”，那么实际执行的顺序就是左边先被完全处理完。要在迭代版里复现同样的顺序，就得先把右区间压栈，再把左区间压栈，这样弹出来的时候左区间先出，和递归的顺序一致。

严格来说，顺序本身不影响正确性——两种顺序排出来的结果都是有序的。但影响两件事：一是调试时的心智模型，如果你希望打印出来的处理轨迹和递归版一致，就必须注意这个顺序；二是栈深度，这一点后面会讲，配合“先小后大”策略时，入栈顺序直接决定了栈深上界能不能压到 O(log n)。所以这不是一个可以随便写的细节，值得在写第一版的时候就固定下来。

2.4 一个生活化的类比：把递归想成“一边切菜一边洗锅”

我给别人讲这个概念时常用一个类比：递归快排像一个厨师做菜，切完一刀立刻转身去处理左半边，处理完左半边再回来处理右半边，脑子里要记住“我还有右半边没弄”，这个“记住”就占用他的脑容量（栈空间）。数据一大，要记的事情一多，脑子就炸了。

非递归版本相当于厨师旁边放了一块白板，切完一刀就在白板上写两行“左半边待办”“右半边待办”，然后从白板上挑一行擦掉去做。白板在桌上（堆内存），想写多少写多少，只要白板够大就不存在“脑子炸掉”的问题。这个类比虽然粗糙，但它精准地传达了核心：非递归不是不算了，而是把记忆的载体从脑子换成了纸。

3. 分区函数：非递归版的地基不能松

3.1 三种分区写法的取舍

非递归改造只动了“调度层”，真正决定性能的还是分区函数。常见的三种写法各有脾气，我按自己的使用体验排一下。

Hoare 原始版（左右指针相向而行，相遇即止）交换次数最少，平均性能最好，但边界条件极其反人类，i <= j还是i < j、返回值是j还是i，写完必须拿小数组暴力对拍才敢用。它的一个隐患是返回值不是基准元素的最终位置，而是一个分界点，用作递归边界时容易写错。

挖坑法（把基准值抠出来，从右边找小的填到左边坑里，再从左边找大的填到右边坑里）逻辑直观，基准最后落在哪个位置一目了然，返回值就是基准下标，非常适合教学和非递归改造。我下面给的代码就是用这个。

前后指针法（Lomuto）代码最短，但它在遇到大量重复元素时性能很差，因为等于基准的元素全被划到一边，分区极度不平衡。而且交换次数比 Hoare 多。

分区写法	平均交换次数	重复元素表现	边界难度	适合场景
Hoare 原始版	最少	较好	高	追求极限性能
挖坑法	中等	中等	低	教学、通用实现
前后指针法	较多	差	最低	代码简洁优先

我选挖坑法不是因为它最快，而是因为非递归版本已经把调度逻辑搞复杂了，分区这块必须选一个自己能一眼看懂、不易写错的。如果你已经在用 Hoare 版且验证充分，直接搬过来也完全没问题，两者在非递归框架里是可以互换的。

3.2 三数取中：一个小动作解决大问题

分区最怕的就是基准选到极值。想象输入是已经升序排好的数组，你每次都取最左边的元素当基准，那么每次分区后右区间是 n-1 个元素、左区间是空的，递归深度直接退化成 n，复杂度变 O(n²)。这不是理论上的极端情况，实际业务里“已经有序的数据”太常见了——数据库导出的、日志按时间追加的，天然有序。

三数取中的做法是：取区间首、中、尾三个元素，比较后把中位数换到lo位置当基准。这样对已经有序的输入，中位数恰好是中间值，分区非常均衡。代价是每个区间多两三次比较，相比于它避免的退化风险，这笔买卖太划算了。

写法上有个小技巧：不要写一堆 if-else 判断三个数的大小关系，直接三次两两交换就够了。先让a[lo] <= a[mid]，再让a[lo] <= a[hi]，此时lo已经是最小的，再让a[mid] <= a[hi]，三个数就排好了，中位数自然落在mid上，把它换到lo即可。三行代码，逻辑清晰，不容易出错。

3.3 挖坑法的实现与不变式

写分区函数时，脑子里要始终维持一个不变式：[lo, i)区间的元素都不大于基准，(j, hi]区间的元素都不小于基准，[i, j]是还没检查的区域，其中有一个位置是“坑”。每轮循环做的就是从右边找一个小于基准的填进左边的坑，再从左边找一个大于基准的填进右边的坑。

具体到代码，我习惯先把基准值抠出来存进临时变量，此时lo位置成为第一个坑：

template <typename T> int partitionRange(std::vector<T>& a, int lo, int hi) { int mid = lo + (hi - lo) / 2; if (a[mid] < a[lo]) std::swap(a[mid], a[lo]); if (a[hi] < a[lo]) std::swap(a[hi], a[lo]); if (a[hi] < a[mid]) std::swap(a[hi], a[mid]); std::swap(a[mid], a[lo]); // 中位数挪到 lo 当基准 T pivot = a[lo]; int i = lo, j = hi; while (i < j) { while (i < j && !(a[j] < pivot)) --j; // 右边找严格小于的 a[i] = a[j]; while (i < j && a[i] < pivot) ++i; // 左边找不小于的 a[j] = a[i]; } a[i] = pivot; return i; }

注意内层两个while里的比较写法。右边用的是!(a[j] < pivot)，等价于a[j] >= pivot，之所以这么写而不是直接写a[j] >= pivot，是为了让这个模板函数对只支持<运算符的自定义类型也能用。左边用的是a[i] < pivot，严格小于，遇到等于基准的元素就停下。这种不对称是有意为之的：它保证了两边指针不会同时越过对方，也让等于基准的元素被均匀地分到两侧，避免重复元素全部堆在一边。

提示：如果你处理的数据里重复值特别多（比如按状态字段排序的订单列表，状态就那么几个值），这个版本依然会退化到 O(n²)。解决办法是改用三路分区，把区间切成“小于”“等于”“大于”三段，这一块在第 6 节细说。

4. 完整实现与参数选择：可以直接抄的版本

4.1 C++ 版本：模板 + 小区间插入排序 + 栈深控制

先说一个很多人会忽略的优化：小区间不值得用快排。当区间长度小于 16 左右时，快排的递归/压栈开销和分区判断开销超过了它的收益，而插入排序在这种小规模、局部有序的数据上极快。原因有两个，一是插入排序的常数因子极小，二是它访问的数据集中在一个小区间内，几乎全部命中 CPU 的 L1 缓存。16 这个数字也不是瞎拍的，一条缓存行通常 64 字节，刚好装 16 个int，这个阈值让整个小区间落在一到两条缓存行里。实际取值在 8 到 24 之间都行，我用 16 用得最顺手。

另一个关键点是栈深控制。前面说过，如果无脑先压左后压右，栈深度最坏还是 O(n)。做法是：分区之后，比较左右两个子区间的长度，先把短的压进去、把长的压进去，然后循环处理短的那个——但因为我们用的是 while 循环而不是真递归，更清晰的实现是“先压长的、后压短的”，这样短的在栈顶会被优先弹出处理。

这里我把逻辑再理一遍，因为这是最容易绕晕的地方。我们的目标是让栈里同时存在的区间数最少。假设每次分区后，我们把较长的区间压栈，较短的那个直接继续在下一轮循环中处理（而不是压栈），那么每一轮处理，问题规模至少减半，最多经过 log₂(n) 轮规模就降到阈值以下，栈里也就积累了 log₂(n) 个“待处理的大区间”。这就是 O(log n) 栈深的由来。实现上，因为不好“直接继续”，一般写成把长的压栈、短的也压栈，但这样就不能保证短的在栈顶了……

更简单可靠的做法是：永远先压左后压右，但压的时候先判断，只压非空区间，同时接受栈深可能略大于 log n 的事实。实际上真正让栈深爆炸的是退化情况，而退化情况已经被三数取中 + 小区间插排大幅缓解了。不过我还是更推荐严格版的写法：

template <typename T> void insertionSort(std::vector<T>& a, int lo, int hi) { for (int i = lo + 1; i <= hi; ++i) { T key = a[i]; int j = i - 1; while (j >= lo && key < a[j]) { a[j + 1] = a[j]; --j; } a[j + 1] = key; } } template <typename T> void quickSortIterative(std::vector<T>& a) { const int THRESHOLD = 16; int n = (int)a.size(); if (n < 2) return; std::vector<std::pair<int,int>> stk; stk.reserve(64); stk.emplace_back(0, n - 1); while (!stk.empty()) { auto [lo, hi] = stk.back(); stk.pop_back(); if (hi - lo + 1 <= THRESHOLD) { insertionSort(a, lo, hi); continue; } int p = partitionRange(a, lo, hi); int leftLo = lo, leftHi = p - 1; int rightLo = p + 1, rightHi = hi; // 关键：长的先压，短的后压，短的在栈顶优先被处理 if (leftHi - leftLo >= rightHi - rightLo) { if (rightLo < rightHi) stk.emplace_back(rightLo, rightHi); if (leftLo < leftHi) stk.emplace_back(leftLo, leftHi); } else { if (leftLo < leftHi) stk.emplace_back(leftLo, leftHi); if (rightLo < rightHi) stk.emplace_back(rightLo, rightHi); } } }

这段代码里if (rightLo < rightHi)这种判断看着啰嗦，但它省掉的是“空区间入栈再出栈”的无谓开销。如果子区间只有一个元素，其实也不需要走插入排序，直接跳过就行。这种细节单次也就省几十纳秒，但在千万级元素的排序里，累积起来是肉眼可见的。

4.2 Python 版本：注意列表操作的开销

Python 版的思路一模一样，但有两点要注意。第一，list.pop()和list.append()都是均摊 O(1)，可以直接当栈用。第二，Python 的函数调用开销远大于 C++，所以非递归版本在 Python 里的收益反而更明显一些，尤其是不可能因为递归深度触发RecursionError（Python 默认递归上限 1000，快排一千万元素必然爆）。

def quick_sort_iterative(arr, threshold=16): if len(arr) < 2: return arr stk = [(0, len(arr) - 1)] while stk: lo, hi = stk.pop() if hi - lo + 1 <= threshold: _insertion_sort(arr, lo, hi) continue mid = lo + (hi - lo) // 2 if arr[mid] < arr[lo]: arr[mid], arr[lo] = arr[lo], arr[mid] if arr[hi] < arr[lo]: arr[hi], arr[lo] = arr[lo], arr[hi] if arr[hi] < arr[mid]: arr[hi], arr[mid] = arr[mid], arr[hi] arr[mid], arr[lo] = arr[lo], arr[mid] pivot = arr[lo] i, j = lo, hi while i < j: while i < j and arr[j] >= pivot: j -= 1 arr[i] = arr[j] while i < j and arr[i] < pivot: i += 1 arr[j] = arr[i] arr[i] = pivot p = i left = (lo, p - 1) right = (p + 1, hi) # 长的先压，短的后压 if left[1] - left[0] >= right[1] - right[0]: if right[0] < right[1]: stk.append(right) if left[0] < left[1]: stk.append(left) else: if left[0] < left[1]: stk.append(left) if right[0] < right[1]: stk.append(right) return arr

Python 版里有个容易踩的坑：arr[j] >= pivot这个比较，如果arr里装的是自定义对象而只实现了__lt__，>=会报错。保险的写法是not (arr[j] < pivot)，和 C++ 版保持一致。另外 Python 的三数取中那段用了连续交换，虽然看着不如 C++ 版本整齐，但逻辑是等价的，mid位置的元素在三次交换后就是中位数。

4.3 参数怎么定：三个数字的来龙去脉

代码里有三个数值得自己拍板，我给出我的理由。

阈值 16：前面提过缓存行的理由。补充一点，如果元素类型不是int而是 8 字节的long或指针，那就换成 8；如果是 4 字节的float，16 仍然合适。原则是“让一个小区间塞进一到两条缓存行”。我用过 8、16、24 三档做对比，在随机数据上差异在 3% 以内，16 是安全区间。

栈的 reserve 大小 64：采用“长的先压、短的后压”之后，栈深上界是log₂(n) + 1。n 到十亿时约 31，n 到 2 的 64 次方（实际中不可能有这么大的数组）才到 64。所以 64 是个绝对安全的上界，一次分配终身使用。如果你不放心，reserve(128)也就多占 1KB，无所谓。

是否要给栈加容量检查：C++ 版用了 vector 所以不用管，如果用裸数组当栈，必须加一个“栈满则扩容”或者断言。这是我踩过的坑之一，早期为了“极致性能”用固定长度数组，结果忘了算退化情况，跑大数据时数组越界。vector 的这点开销相比于它提供的安全性，完全不值得省。

5. 实测对比与性能数据分析

5.1 我跑的几组数据

为了让自己心里有底，我在一台开发机上做了几组对比，C++ 实现，-O2优化，元素类型int，每组跑 10 次取中位数。数据规模分别是十万、一百万、一千万，场景分为“完全随机”“已经升序”“全部元素相同”三种。下面的表是相对耗时（以递归版在随机十万数据上的耗时为 1.0 基准）。

场景	数据规模	递归版相对耗时	非递归版相对耗时	是否爆栈
完全随机	10 万	1.00	1.02	否
完全随机	100 万	10.4	10.6	否
完全随机	1000 万	108	110	否
已经升序（带三数取中）	1000 万	112	114	否
全部相同（二路分区）	10 万	巨大	巨大	递归版超时前先爆栈
完全随机（无阈值优化）	1000 万	119	124	是，递归版溢出

从这个表能读出两件事。第一，在随机数据上非递归版本并没有更快，那 2% 左右的差距就是显式栈多出来的内存读写成本，属于预期之内。第二，递归版的爆栈是真实存在的风险，尤其是在没有做任何优化、又碰上退化输入的时候，一千万数据量下它不是“可能”溢出，而是“稳定”溢出。

那个“全部相同”的场景特别值得说。二路分区的挖坑法遇到全相同元素时，每次分区都只能切掉一个元素（因为等于基准的都跑到一侧去了），n 个元素就需要 n 轮分区，复杂度 O(n²)。十万个相同元素，递归版跑到栈溢出也没排完，非递归版虽然不会爆栈，但会跑很久。这就引出了下一个必须处理的问题。

5.2 三路分区：重复元素的解药

三路分区的思路是把区间分成三段：[lo, lt-1]全部小于基准，[lt, gt]全部等于基准，[gt+1, hi]全部大于基准。等于基准的那一段在后续轮次里完全不用再处理，这就彻底干掉了重复元素导致的退化。

在非递归框架里，三路分区的改造非常自然：一次分区产出两个新区间，把这两个压栈就行，逻辑框架没有任何变化。

// 返回 (lt, gt)，[lt, gt] 区间内元素都等于基准 template <typename T> std::pair<int,int> partition3Way(std::vector<T>& a, int lo, int hi) { T pivot = a[lo]; int lt = lo, i = lo + 1, gt = hi; while (i <= gt) { if (a[i] < pivot) std::swap(a[lt++], a[i++]); else if (pivot < a[i]) std::swap(a[i], a[gt--]); else ++i; } return {lt, gt}; }

对应的调度代码只需改两行：把partitionRange换成partition3Way，然后把[lo, lt-1]和[gt+1, hi]这两个区间压栈。注意[lt, gt]这一段被直接丢弃了，这正是性能提升的来源。

实测下来，十万个全相同元素，二路分区需要几秒甚至更久（取决于实现），三路分区只需要毫秒级——因为一次分区就把整个数组处理完了，lt=0, gt=n-1，两个子区间都是空的。这个对比非常震撼，也是我后来在所有需要处理“分类别排序”场景时都默认上三路的原因。

注意：三路分区不总是更优。在元素全部互不相同的数据上，它多做了一些比较，比二路版本慢 5% 到 10%。所以别盲目上，要看你的数据分布。业务字段排序、日志级别排序这类“值域很小”的场景，三路是必选。

6. 常见问题与排查技巧实录

6.1 死循环：八成是分区函数的边界写错了

非递归版最常见的 bug 是死循环，程序不崩、CPU 拉满、就是不结束。排查时的第一反应应该是：会不会压进去的区间和弹出来的区间是同一个？逻辑上，只要分区函数返回的基准位置p严格落在[lo, hi]内，那么[lo, p-1]和[p+1, hi]的长度都严格小于原区间，问题规模必然缩小，不可能死循环。反过来说，如果p等于hi或者等于lo - 1，就会压出一个长度不变的区间，死循环成型。

所以排查路径很清楚：在压栈前打个日志，把(lo, hi, p)三个值打出来，看是否有p == hi且hi > lo的情况。有的话就是分区函数的指针走位错了。我遇到过两次，一次是内层while的条件写成了a[j] > pivot（应该是>=的等价写法），导致等于基准的元素一直被跳过，指针跑出边界；另一次是三数取中的交换写漏了一句，基准根本不是中位数。

第二个死循环来源是栈的弹出和压入不配对。比如你在continue之前忘了已经pop_back，或者在某条分支里重复压了同一对区间。这种 bug 的特征是栈的大小持续增长，跑一会儿内存就上去了。加一个“栈大小超过 1000 就断言失败”的检查非常有效，因为正常情况下栈深不会超过 64。

6.2 结果局部有序但整体不对：栈处理顺序的锅

有一种 bug 特别隐蔽：程序跑完了，数组看起来“差不多有序”，但验证时发现有少数元素位置不对。这种问题往往出在区间边界的开闭约定不一致。比如分区函数返回的p是“基准的最终位置”，那么左区间应该是[lo, p-1]、右区间是[p+1, hi]；但如果你的分区函数返回的是“分界点”，左区间可能是[lo, p]、右区间是[p+1, hi]。两种约定混用，就会漏掉或重复处理某个元素。

我的建议是：在函数注释里明确写死这个约定，并且永远用同一个约定。我自己的习惯是分区函数返回基准的最终下标，左闭右闭，这样的话边界处理最直观。另外，验证正确性时不要只看“数组是否有序”，还要看“元素的多重集合是否一致”——万一你的代码丢元素了呢？用一个std::is_sorted加一个计数校验，两个都过才算真对。

6.3 性能不如预期：先看数据分布，再看阈值

有朋友反馈说他的非递归快排比std::sort慢了好几倍，问我是不是非递归本身有问题。我看了代码，问题出在他的测试数据是“大量重复的小整数”，而他用的是二路分区。换成三路分区之后，性能立刻追平。所以遇到性能问题，排查顺序应该是这样的：先确认数据分布（是否有大量重复、是否基本有序），再确认分区策略是否匹配，最后才看阈值、栈的实现这些细节。

还有一个容易被忽略的点是编译优化的影响。在-O0下跑基准测试毫无意义，因为函数调用、std::pair的构造析构全都没被优化，非递归版本的显式栈操作成本会被放大好几倍。我见过有人拿 debug 构建的数据下结论说“非递归慢 30%”，这是典型的测量误差。测试必须用-O2或-O3，并且用 release 配置。

6.4 常见问题速查表

现象	最可能的原因	排查手段
程序不结束，CPU 100%	分区返回值导致区间未缩小	打印(lo, hi, p)，检查p是否等于hi
栈持续增长，内存上涨	压栈分支重复或未弹出	加栈深断言，正常不超过 64
结果基本有序但少数错位	区间开闭约定不一致	校对分区返回值语义，统一为“基准最终下标”
元素丢失或重复	压栈时漏了或多算了一个位置	排序后做多重集合计数校验
重复元素多时极慢	用了二路分区	换三路分区
整体比标准库慢很多	未做小区间插排 / 用了 debug 构建	检查阈值分支和编译选项
小数组排序结果错误	插入排序的起点或边界写错	单独对插入排序做单元测试

提示：这张表里的每一条我几乎都真实踩过。最省时间的做法是写一个 20 行的暴力对拍脚本，拿 100 组随机小数组（长度 0 到 30，元素范围 0 到 5）逐组比对结果和标准库的输出。小数组能覆盖绝大部分边界 bug，重复元素范围小能触发三路分区的问题，跑一次只要几百毫秒，比肉眼 debug 快十倍。

7. 我在这套实现上的一些个人取舍

最后聊几个不是“对错”而是“口味”的选择，可能对你在自己项目里落地时有参考价值。

关于要不要写成模板。我把 C++ 版写成了模板，好处是int、double、std::string都能直接用，坏处是编译期实例化会膨胀，而且模板错误信息极其难读。如果你的项目只需要排一种类型，我建议去掉模板，直接写具体类型，代码体积能小不少，调试也方便。模板的收益在库代码里才明显，业务代码里往往是负担。

关于是否要做内省排序。std::sort用的是内省排序（introsort）：快排 + 堆排 + 插排三合一，用一个深度计数器监控递归深度，一旦超过2 * log₂(n)就切换成堆排序，保证最坏情况也是 O(n log n)。在非递归框架里加这个其实很容易，因为深度计数器可以从栈的大小推出来（栈深反映了当前未处理的分支数）。我做过一版，代码量增加约 30 行，代价是常数开销略微上升。除非你的输入可能被恶意构造（比如做在线服务需要对用户提交的数据排序），否则我不太推荐加——三数取中 + 三路分区已经把退化概率压得很低了，内省排序更多是“确定性保证”的价值，而非实用性能价值。

关于用数组还是 vector 做栈。我见过有人用std::stack<std::pair<int,int>>，功能上没问题，但std::stack默认底层是std::deque，每次 push/pop 有额外的间接层。用std::vector加emplace_back/pop_back更快也更简单。这种细节在小数据量上看不出差别，但在千万级排序里能差出几十毫秒。

关于和递归版的取舍。我的实际做法是：对外提供的排序 API 内部默认走递归版 + 三数取中 + 小区间插排，因为这个组合代码最短、最好维护；只在明确知道数据量可能极大、或者运行环境栈空间受限（比如某些嵌入式和协程环境）时，才切到非递归版。换句话说，非递归版是我的“保险丝”，不是“默认档位”。想清楚这一点，就不会在两种实现之间反复纠结了。

顺带说一句，如果你把这份代码拿去面试场景，面试官大概率会追问“怎么保证栈深不超过 log n”。这时候回答的重点不是代码怎么写，而是把“每轮至少有一半的问题规模被立即处理掉，只有另一半进栈，所以栈中元素个数不超过 log₂(n)”这个论证讲清楚。代码可以写得朴素，但这个推理必须能脱口而出，因为它才是非递归版本真正的设计内核。