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 ?