Prove by weak induction on the quantity (n + m) that the merge algorithm in Figure 5.30 satisfies the following property for any n ≥ 0 and m ≥ 0: given any two sorted arrays X[1 . . . n] and Y[1 . . ....

Prove by weak induction on the quantity (n + m) that the merge algorithm in Figure 5.30 satisfies the following property for any n ≥ 0 and m ≥ 0: given any two sorted arrays X[1 . . . n] and Y[1 . . . m] as input, the output of merge(X,Y) is a sorted array containing all elements of X and all elements of Y.