请问F#归并排序实现的split函数递归分支运行原理是什么？

1. 基础语法疑问解答 #

• 关于a :: b :: cs的含义
  F#中::是右结合的列表拼接运算符，a :: b :: cs等价于a :: (b :: cs)，这个模式匹配的是长度≥2的列表，不是你理解的长度≥3：
  • a 对应列表第一个元素
  • b 对应列表第二个元素
  • cs 对应列表剩余元素组成的子列表，当原列表长度刚好为2时，cs是空列表[]
• 关于in关键字的用法
  这是F#的本地绑定语法，let 绑定 in 表达式的含义是：先计算let后定义的绑定值，这个值仅在in后面的表达式作用域内有效，整个表达式的返回结果就是in后表达式的计算结果。你给出的代码里，就是先递归调用split cs得到两个子列表组成的元组(r, s)，再计算返回(a :: r, b :: s)。

2. 递归拆分逻辑运行原理 #

这个递归逻辑的本质是把原列表的奇数位置元素和偶数位置元素分别放到两个子列表中，最终两个子列表的长度差最多为1，正好满足归并排序对半拆分的要求，我们用一个具体的例子走完全程就很清晰：

示例输入列表：[1;2;3;4;5]

1. 第一层匹配：a=1、b=2、cs=[3;4;5]，递归调用split [3;4;5]
2. 第二层匹配：a=3、b=4、cs=[5]，递归调用split [5]
3. 第三层匹配单个元素分支，直接返回([5], [])
4. 第二层拿到返回值(r=[5], s=[])，返回(3::[5], 4::[]) = ([3;5], [4])
5. 第一层拿到返回值(r=[3;5], s=[4])，返回(1::[3;5], 2::[4]) = ([1;3;5], [2;4])

可以看到最终拆分出来的两个子列表长度分别为3和2，正好是原列表长度的一半左右，完全符合归并排序的拆分要求。这种拆分方式只需要遍历列表一次，比先计算列表长度再截取前后半段的实现效率更高。

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