分治排序的正确性证明

Question

假设我们有一个排序方法：

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);
   }  
}

我们可以用什么方法来证明排序算法对数组a的排序是正确的还是错误的？有没有系统的方法来解决这个问题？我知道它适用于size_a==1和size_a==2的情况，但如果size_a是，比如说，30，那么我们递归地调用数组的~2/3大小的chuked上的排序方法。它看起来似乎有效，但我不知道如何正式证明这一点。

Answer 1

你必须证明这些线

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

将对整个数组从x到y进行排序，假设三个调用中的每一个都将正确地对数组的给定子集进行排序。三个调用中的最后一个确保元素从x到y-s是有序的。第二个调用确保对从y-s到y的元素进行排序。要得出所有元素都是有序的结论，你需要证明从y-s到y的元素比从x到y-s的元素大。

这是真的，因为：第一个调用确保较大的s元素将超出索引y-s-s>=x+s。因此，第二个调用将把它们发送到数组的末尾。

如果数组的长度正好是3*s，那么所有这些推理都是正确的。如果s小于长度的三分之一，则仍然成立，事实上，如果s较小，则排序的子集较大。