SML递归快速排序代码中split函数两次调用的疑问

首先贴出代码：

fun quicksort nil = nil
|   quicksort (pivot :: rest) =
    let
        fun split(nil) = (nil,nil)
        |   split(x :: xs) =
            let
                val (below, above) = split(xs)
            in
                if x < pivot then
                    (x :: below, above) 
                else
                    (below, x :: above)
                end;
                val (below, above) = split(rest)
    in
        quicksort below @ [pivot] @ quicksort above
    end;

1. 为什么split函数会在quicksort函数中被调用两次？ #

这两次调用属于完全不同的层级场景，并非重复执行同一逻辑：

• 第7行的调用是split函数自身的递归调用：split是递归实现的分割函数，要完成整个列表的分割，必须先递归处理当前元素的剩余子列表xs，拿到子列表的分割结果后，才能确定当前元素x的分组位置。
• 第14行的调用是quicksort对split的顶层调用：quicksort选定基准值pivot后，需要把剩下的所有元素rest分成两组，这时候直接调用split完成整体分割，为后续递归排序两个子列表做准备。

2. 每次调用split函数分别实现什么功能？ #

• 第7行val (below, above) = split(xs)：
  这是split的递归子步骤，负责将当前元素x之后的子列表xs，分割成两个子列表——below（所有小于pivot的元素）和above（所有大于等于pivot的元素）。拿到这个结果后，再根据x和pivot的大小关系，把x插入到对应的分组中，逐步完成整个输入列表的分割。
• 第14行val (below, above) = split(rest)：
  这是quicksort的核心分割步骤，负责将除基准值pivot之外的所有剩余元素rest，一次性分割成两个列表：below包含所有小于pivot的元素，above包含所有大于等于pivot的元素。之后quicksort会递归排序这两个子列表，再和pivot拼接成最终的有序列表。

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