Proof of correctness for divide and conquer sort

Question

Suppose we have a sorting method:

void DD_sort(int a[], int x, int y, int size_a)
{
   if(x == y){
      return;
   }
   else if(y == x+1){
      if(a[x] > a[y]){
         /* swap the content */
         return;
      }
   }
   else{
      int s = floor((y+1-x)/3);
      DD_sort(a, x, y-s, s);
      DD_sort(a, x+s, y, s);
      DD_sort(a, x, y-s, s);
   }  
}

What methods can we use to show that the sorting algorithm correctly or incorrectly sorts the array a? Are there any systematic approaches to this problem? I understand that it works in the case of size_a == 1 and size_a == 2, but if size_a is, say, 30, then we're recursively calling the sorting method on ~2/3-sized chucked of the array. It appears as if it works, but I'm not sure how to formally show that.

Answer 1

You have to prove that these lines

  DD_sort(a, x, y-s, s);
  DD_sort(a, x+s, y, s);
  DD_sort(a, x, y-s, s);

will sort the entire array from x to y, given that each of the three calls will correctly sort the given subset of the array. The last of the three calls ensures that the elements from x to y-s are ordered. The second call assures that the element from y-s to y are ordered. To conclude that all elements are ordered you need to show that the elements from y-s to y are larger than the elements from x to y-s.

This is true because: the first call ensures that the larger s elements will go beyond index y-s-s >= x+s. So the second call will send them to the end of the array.

All this reasoning is correct if the length of the array is exactly 3*s. It remains true if s is smaller than a third of the length, in fact if s is smaller the sorted subsets are larger.