mergeSortと一緒に必要な基本ケース

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）。