如何使用数学归纳法证明合并工作?

第一个假设:您使用的合并例程将两个排序后的数组合并为一个排序后的数组. 第二个假设:合并例程终止

First assumption: the merge routine you use merges two sorted arrays into a sorted array. Second assumption: the merge routine terminates

• 基本情况: n = 1，始终对1个元素的数组进行排序
• 归纳假设:合并排序适用于n = 1,2，...，k
• 归纳步骤: n = k + 1

• Base case: n = 1, array of 1 element is always sorted
• Inductive hypotshesis: merge sort works for n = 1,2,...,k
• Inductive step: n = k+1

现在我们需要证明归纳步骤是正确的.

Now we need to prove the inductive step is correct.

合并排序将数组分为两个子数组L = [1,n/2]和R = [n/2 + 1, n].根据上述事实，可以看到ceil(n/2)小于k.根据我们的归纳假设，对L和R的合并排序的结果均正确排序(因为它们在[1,k]范围内).此外，根据我们的假设，合并例程将它们合并为包含所有元素的已排序数组，因为size(L) + size(R) = n，因此这意味着它已正确排序了大小为n = k+1的数组.

Merge sort splits the array into two subarrays L = [1,n/2] and R = [n/2 + 1, n]. See that ceil(n/2) is smaller than k based on the facts above. By our inductive hypothesis both results of merge sort for L and R are correctly sorted (as they are within [1,k] range). Furthermore from our assumption merge routine merges them into a sorted array which contains all elements because size(L) + size(R) = n so this means that it correctly sorted an array of size n = k+1.

@Edit:对不起，未读.对于合并部分:

@ sorry, missread. For the merge part:

在这里，我们将进行多维归纳.

Here we will have a multidimensional induction.

假设:输入数组X，Y已排序

Assumption: input arrays X,Y are already sorted

• 基本情况: size(X)== 0&& size(Y)> = 0 =>返回Y || size(Y)== 0&& size(X)> = 0 => X，这是正确的，因为X和Y都已排序，并且将排序后的数组与空数组合并会产生相同的非空数组
• 关于X的归纳假设:合并适用于merge(n，size(Y))，其中n = 1,2,3，...，k&&大小(Y)> = 0
• 关于Y的归纳假设:合并适用于merge(size(X)，m)，其中m = 1,2,3，...，l&&大小(X)> = 0
• 感应式越过X: n = k + 1
• 对Y的归纳步进: m = l +1

• Base case: size(X) == 0 && size(Y) >= 0 => return Y || size(Y) == 0 && size(X) >= 0 => X, this is true as both X and Y are sorted and merging a sorted array with an empty array yields us the same non-empty array
• Inductive hypothesis over X: merge works for merge(n, size(Y)) where n = 1,2,3,...,k && size(Y) >= 0
• Inductive hypothesis over Y: merge works for merge(size(X), m) where m = 1,2,3,...,l && size(X) >= 0
• Inductive step over X: n = k + 1
• Inductive step over Y: m = l + 1

对于X上的第一个归纳步骤，除了基本情况外，我们还有2种情况:

For the first induction step over X we have 2 cases, besides the base case:

• X [1]< Y [1] => X[1] ⊕ merge(tail(X), Y) =>根据我们对X的假设，这是正确的，因为merge(k, size(Y))是正确的，并且我们将较小的元素放在前面，因此我们保持顺序
• X [1]> = Y [1] => Y[1] ⊕ merge(X, tail(Y)) =>这里有两个选择:
  • size(tail(Y)) = 0 =>我们遇到了一个基本案例，因此该案例被证明是正确的
  • size(tail(Y)) > 0 =>我们进一步递归，最终找到了基本情况或merge(tail(X), subarray(Y))，其中归纳假设证明了size(tail(X)) = k =>
  • X[1] < Y[1] => X[1] ⊕ merge(tail(X), Y) => this is true as merge(k, size(Y)) is true according to our hypothesis over X and we are putting the smaller element at the front so we are keeping the order
  • X[1] >= Y[1] => Y[1] ⊕ merge(X, tail(Y)) => here we have two options:
    • size(tail(Y)) = 0 => we hit a base case thus this case is proven to be correct
    • size(tail(Y)) > 0 => we recurse further finally hitting the base case or merge(tail(X), subarray(Y)) where size(tail(X)) = k => is proven by our inductive hypothesis

    类似地，Y上的感应步进:

    Similarly for induction step over Y:

    • X [1]> = Y [1] => Y[1] ⊕ merge(X, tail(Y)) => this is true by our hypothesis merge(size(X)，l)`是正确的，我们将较小的元素放在前面
    • X [1]< Y [1] => X[1] ⊕ merge(tail(X), Y) =>这里有两个选择:
      • size(tail(X)) = 0 =>我们遇到了一个基本案例，因此该案例被证明是正确的
      • size(tail(X)) > 0 =>我们进一步递归，最终找到了基本情况或merge(subarray(X), tail(Y))，其中我们的归纳假设证明了size(tail(Y)) = l =>
      • X[1] >= Y[1] => Y[1] ⊕ merge(X, tail(Y)) => this is true by our hypothesismerge(size(X), l)` is true and we are putting the smaller element at the front
      • X[1] < Y[1] => X[1] ⊕ merge(tail(X), Y) => here we have two options:
        • size(tail(X)) = 0 => we hit a base case thus this case is proven to be correct
        • size(tail(X)) > 0 => we recurse further finally hitting the base case or merge(subarray(X), tail(Y)) where size(tail(Y)) = l => is proven by our inductive hypothesis

        该算法会在我们将其中一个数组缩小1个元素的每一步时终止，因此其中一个最终会击中我们的基本情况

        The algorithm terminates as at each step we are making one of the arrays smaller by 1 element, thus one of them will eventually hit our base case