CODEWITHSUNDEEP
algorithmmath
Ugluk
Ugluk

Reputation: 77

How do I prove merge works using mathematical induction?

Here is the link to my homework.

I just want help with the first problem for merge and will do the second part myself. I understand the first part of induction is proving the algorithm is correct for the smallest case(s), which is if X is empty and the other being if Y is empty, but I don't fully understand how to prove the second step of induction: showing merge is correct with input sizes k + 1.

I've done induction before on equations, never on an algorithm.

Thanks!

Upvotes: 1

Views: 15202

Answers (1)

Mateusz Dymczyk
Mateusz Dymczyk

Reputation: 15141

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

  • 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.

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.

Assumption: input arrays X,Y are already sorted

  • 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

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) => 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

Similarly for induction step over Y:

  • 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

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

Upvotes: 6

Related Questions