澄清合并排序所需的基本情况

Question

我知道这是一个很简单的问题，但我是自学的，所以请多多包涵！

在维基百科的 mergeSort 伪代码中（见下文），最终情况是数组/列表的长度小于或等于 1。在评论中，他们说如果它的长度为 0 或 1，那么它就会被排序。我同意这一点，但我很好奇这是否意味着如果代码具有 if (length == 1)，mergeSort 将无法工作？我只是对一个数组如何可能拆分为 0 长度数组感到困惑。如果它的长度等于1，它不会已经停止了吗？

function merge_sort(list m)
    // Base case. A list of zero or one elements is sorted, by definition.
    if length of m ≤ 1 then
        return m

    // Recursive case. First, divide the list into equal-sized sublists
    // consisting of the even and odd-indexed elements.
    var left := empty list
    var right := empty list
    for each x with index i in m do
        if i is odd then
            add x to left
        else
            add x to right

    // Recursively sort both sublists.
    left := merge_sort(left)
    right := merge_sort(right)

    // Then merge the now-sorted sublists.
    return merge(left, right)

Answer 1

该算法是递归的，这意味着函数会拆分列表，然后用每个部分调用自身。要终止递归，if (length == 1) 就足够了，因为拆分的结果永远不会是空列表。你没看错。

但是用户可以用空列表调用这个函数。所以这也需要被抓住。因此 if (length <= 1) (if length of m ≤ 1 then return m).

澄清合并排序所需的基本情况

Clarificaiton of base case needed with mergeSort

mergesort