# Proof that this sorting algorithm sorts the input

I'm given this "sorting" algorithm and now I'm supposed to prove, that if given an array of integers of length $$n$$, sort(A,0,n-1) will sort it.

def sort (A ,i ,j ):
if ( i +1 < j ):
k = (j - i +1) // 3
sort (A , i , j -k )
sort (A , i +k , j )
sort (A , i , j -k )
else:
if ( A [i] > A [j]):
swap( A[i] , A [j])


I don't really know how to tackle this question. I know you're supposed to show that the algorithm terminates and then find some loop-invariant to show that the algorithm does what it's supposed to do. Maybe I could apply some induction here ?

• – Yuval Filmus May 22 at 20:07
• Well thanks alot! – Christian Singer May 22 at 20:13