非尾递归快速排序未触发栈溢出的原因探究（基于SBCL）

为什么100万元素没触发栈溢出？ #

你的快排递归深度完全由pivot的划分效果决定：

• 随机数组的划分特性：你用random-array生成的数组是随机分布的，选首元素作为pivot时，期望上每次能把数组分成接近1:1的两部分，递归深度是**O(log n)**级别。100万元素的log₂值约为20，1000万也才约24，这个递归深度远低于SBCL默认栈能承载的层数（SBCL默认栈大小通常在8MB左右，每个栈帧仅占用几十字节，轻松支持数千层递归）。
• SBCL的栈默认配置：SBCL对栈的默认限制比较宽松，常规的log级递归完全不会触及栈上限。

1000万元素时SLIME断开的可能原因 #

SLIME显示“Lisp disconnected”不一定是栈溢出，更可能是以下情况：

• 内存资源耗尽：1000万元素的数组本身占用不小内存（比如每个整数占8字节就是80MB），加上SBCL运行时的内存开销，若系统剩余内存不足，进程可能被操作系统强制终止，导致SLIME连接断开。
• SLIME连接超时：长时间无输出的计算可能触发Emacs与SBCL之间的连接超时，尤其是在计算耗时较久的情况下，Emacs会判定连接失效。
• 极端情况的潜在问题：虽然随机数组几乎不会出现，但如果某次pivot划分极端失衡（比如刚好生成接近有序的数组），递归深度会飙升到O(n)，这时候才会触发栈溢出，但这种概率极低。
• 代码边界漏洞：可以检查partition函数的循环逻辑，比如当所有元素等于pivot时，是否能正确退出循环（从代码看，当j走到b时会触发loop-finish，逻辑是对的，但可以手动构造全相等数组测试）。

验证与排查方法 #

1. 测试最坏情况：生成一个完全有序的数组传入快排，此时递归深度为O(n)，必然会触发栈溢出，以此验证你的非尾递归实现确实存在栈溢出风险，只是随机场景没触发。
2. 调整栈大小测试：手动缩小SBCL的栈限制，比如执行(setf sb-ext:*stack-size* (* 1024 1024))（设置为1MB），再跑100万元素的快排，此时log级递归也可能触发溢出，直观感受栈的限制。
3. 脱离SLIME运行：直接在终端启动SBCL执行排序代码，看是否会输出明确错误（栈溢出会提示Stack overflow，内存不足会有系统OOM提示），避免SLIME连接问题干扰判断。
4. 优化pivot选择：如果想降低最坏情况概率，可以改成三数取中选择pivot，减少极端失衡的可能性。

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