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 )
   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 ?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.