Prove that the following recursive algorithm actually sorts

Prove that the following recursive algorithm actually sorts its input:

Prove that the following recursive algorithm actually sorts its input: 3PASS-SORT (A [0], ..., A[n - 1]): if n = 2 and A[0] > A[1] swap A[0] with A[1] else (n > 2) m = ceiling(2n/3) 3PASS-SORT(A[0], ..., A[m - 1]) 3PASS-SORT(A[n - m], ..., A[n - 1]) 3PASS-S0RT(A[0], ..., A[m - 1])

Solution

For the recursive call we are actually diviing the array in to 3 parts. Let us call them A1,A2,A3. In the first recursive call we are sorting A1 and A2. So now all the elements in A1 are less than all the elements in A2. Next we are sorting A2 and A3 combined. So now the greatest elements in A2 and A3 are now in A3. So now all the elements in A3 are greater than A1 and A2. In the next step we sort A1 and A2 again. So the whole array is sorted.