57.7万行文件按年份排序：递归merge sort栈溢出求高效替代算法

Hey there! Let's break down how to fix your stack overflow issue while getting lightning-fast sorting for your 577k-row dataset.

核心问题分析 #

递归版归并排序之所以会触发stack memory overflow，是因为递归调用的深度随着数据量增大而增加——对于577k元素，递归深度大概在19层左右（log2(577000) ≈ 19），但如果你的语言默认栈空间较小，或者链表节点的递归处理逻辑额外占用了栈资源，就容易撞上限。

不过这里有个超级关键的信息你提到了：年份范围仅为1730-2013，总共只有2013 - 1730 + 1 = 284个不同的年份值。这直接给了我们一个最优解的突破口——用计数排序（Counting Sort）或者桶排序（Bucket Sort），完全规避递归，时间复杂度接近O(n)，绝对不会出现栈溢出。

最优实现方案：基于年份的桶排序（适配双向链表） #

因为年份是连续且范围极小的离散值，用数组做桶效率最高，步骤如下：

• 初始化桶数组
  创建一个长度为284的数组，每个元素对应一个年份的空双向链表（或者直接存该年份节点的首尾指针，节省空间）。比如索引0对应1730年，1对应1731年，以此类推，节点年份对应的索引计算公式为：bucket_index = node.year - 1730

• 遍历原链表，分配节点到对应桶
  从头遍历你的双向链表，对每个节点：算出对应的桶索引，将节点从原链表中移除（调整前后节点的指针），再将节点添加到对应桶的双向链表尾部（同一年份的节点保留原顺序即可）

• 串联所有桶，生成排序后的链表
  初始化一个空的结果双向链表（或复用原链表结构），按索引从0到283的顺序遍历桶数组：如果当前桶的链表不为空，就把它的首尾节点连接到结果链表的尾部，同时调整双向链表的prev和next指针，确保整个链表的双向结构正确

为什么这比归并排序更好？ #

• 无递归，彻底避免栈溢出：整个过程都是迭代操作，完全不依赖调用栈
• 时间效率碾压：O(n + k)的时间复杂度，其中k=284，几乎是线性时间，比归并排序的O(n log n)快得多，处理577k数据几乎瞬间完成
• 空间开销极小：桶数组只需要284个元素，不需要额外复制大量节点数据，只是调整指针

备选方案：迭代版归并排序 #

如果你因为某些原因必须用归并排序（比如需要保持通用排序逻辑），可以把递归版改成迭代版归并排序——通过手动模拟栈或者分块处理的方式，避免递归调用带来的栈占用。不过在这个场景下，它的效率还是远不如桶排序，所以只作为备选。

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