Prove that the following algorithm is correct: Considering the sorting problem, we have a list of n integers A = (v1, v2, · . vn). We want to sort the array using insertion sort whose pseudo-code is...

how i prove this algorithm or insertion sort by  induction

Extracted text: Prove that the following algorithm is correct: Considering the sorting problem, we have a list of n integers A = (v1, v2, · . vn). We want to sort the array using insertion sort whose pseudo-code is as follows: note n := A.length denotes the size of the array, number of items. Algorithm 2 INSERTION-SORT(A) for i = 1 to n – 1 do j+i - 1 while A[j] > A[j+1] ^ j > 0 do swap (A[j], A[j + 1]) j+j – 1 end while end for