什么是link arrays？请详解归并排序中link arrays的逻辑、用途与原理

一、什么是链接数组？ #

链接数组本质是用数组下标模拟链表指针的结构：

• 搭配原始数据数组arr，我们会维护一个link数组，link[i]的值代表原始数组中第i个元素的「下一个元素的下标」。
• 不需要像真正的链表那样动态分配节点，完全依托数组的连续内存实现链表的逻辑关系。

二、归并排序里为什么要用链接数组？ #

普通归并排序的核心痛点是合并阶段需要频繁移动元素，如果原始数组存储的是大体积数据（比如复杂对象），移动成本会极高。链接数组刚好解决这个问题：

• 不需要移动原始数组里的元素，只需要修改link数组里的下标指向，就能调整元素的顺序。
• 内存开销小，不需要额外开辟大量临时空间存储合并后的元素，link数组的大小仅和原始数组一致。

三、链接数组版归并排序的工作原理 #

核心思路是把归并排序的「元素移动」替换成「指针（下标）重定向」，分为两个阶段：

1. 拆分阶段 #

和普通归并排序逻辑一致：递归把数组拆分成左右两个子区间，直到每个子区间只剩一个元素。

• 单个元素的link会指向一个特殊标记（比如-1表示链表尾部）。

2. 合并阶段（核心差异点） #

假设要合并两个有序的「链接子链表」，左链表头为left_start，右链表头为right_start：

• 初始化一个临时变量作为「虚拟头节点」，再用current变量跟踪合并后链表的尾部。
• 循环比较左链表当前元素arr[left_start]和右链表当前元素arr[right_start]：
  • 如果左元素更小，就把current对应的link指向left_start，然后left_start移动到link[left_start]（左链表的下一个元素下标）。
  • 如果右元素更小，就把current对应的link指向right_start，然后right_start移动到link[right_start]。
  • 每次操作后，current都更新为刚指向的那个下标。
• 当其中一个子链表遍历完毕，把current的link指向另一个子链表剩余的头节点。
• 最后返回合并后的链表头节点（虚拟头节点的下一个下标）。

四、对应代码的逻辑拆解 #

你提到的那段代码核心就是维护link数组，递归拆分后通过合并函数调整下标指向：

• 初始状态下link[i] = i+1，即每个元素的下一个元素是数组的下一个位置，最后一个元素的link设为-1。
• 递归拆分时，不是直接拆分数组本身，而是拆分link链表的区间范围。
• 合并函数全程不修改原始数组的元素，只通过修改link的下标值，把两个有序链表拼接成一个有序链表。

举个简单例子：
原始数组arr = [3,1,2]，初始link = [1,2,-1]
拆分后左链表是0（对应元素3），右链表是1->2（对应元素1->2）
合并过程：

1. 比较3和1，将current指向1，current移到1
2. 比较3和2，将current指向2，current移到2
3. 右链表遍历完毕，将current指向0
   最终link变为[-1,2,0]，遍历顺序为1->2->3，实现排序。

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