2.2.16自然的归并排序。编写一个自底向上的归并排序，当需要将两个子数组排序时能够利用数组中已经有序的部分。首先找到一个有序的子数组(移动指针直到当前元素比上一个元素小为止)，然后再找出另一个并将它们归并。根据数组大小和数组中递增子数组的最大长度分析算法的运行时间。

import java.util.Arrays;

public  class E2d2d16

{

    public static void sort(Comparable[] a)

    {

      int N=a.length;

      if(N<=1) return;

      Comparable[] aux=new Comparable[N];

      int lo=0;

      int sp=-1;

      int hi=0;

      while(!(lo==0 && sp==N-1))

      {

        lo=0;

        while(lo<N-1)

        {

          sp=FindAscIndex(a,lo);

          hi=FindAscIndex(a,sp+1);

          if(sp==hi)

             break;

          else

           {

            merge(a,aux,lo,sp,hi);

            lo=hi+1;

          }//end if

        }//end while

      }//end while

    }

    

    private static int FindAscIndex(Comparable[] a,int lo)

    {

      int N=a.length;

      if (lo==N-1) return lo;

      else if(lo>N-1) return lo-1;

      int i;

      for(i=lo+1;i<N && !less(a[i],a[i-1]);i++);

      return i-1;  

    }

     

    private static void merge(Comparable[] a,Comparable[] aux,int lo,int sp,int hi)

    {

       for(int i=lo;i<=hi;i++)

         aux[i]=a[i];

       //

       int i=lo;

       int j=sp+1;

       for(int k=lo;k<=hi;k++)

       {

         if(i>sp) a[k]=aux[j++];

         else if(j>hi) a[k]=aux[i++];

         else if(less(aux[j],aux[i])) a[k]=aux[j++];

         else a[k]=aux[i++];

       }

    }

   

    public static boolean isSorted(Comparable[] a)

    {

      int N=a.length;

      for(int i=1;i<N;i++)

        if(less(a[i],a[i-1])) return false;

      return true;

    }

   

    private static boolean less(Comparable v,Comparable w)

    {

        return v.compareTo(w)<0;

    }

   

    public static void main(String[] args)

    {

      Integer N=Integer.parseInt(args[0]);

      Comparable[] a =new Comparable[N];

      for(int i=0;i<N;i++)

        a[i]=StdRandom.uniform();

      sort(a);

      StdOut.printf("a size is:%d,a is sorted=%s",a.length,isSorted(a));

   }

  

}

分析：

最坏情况：数组为逆序时，可以确保参与第一轮的归并的所有子数组的长度均为1,时此即为最坏情况。设数组长度为N=2^n,那么归并树深度为n,每一层查找子数组需要进行2N次数组访问，每一层归并需要2N次数组访问完成复制到辅助数组的操作，需要2N次数组访问完成比较，需要2N次访问完成辅助数组到a数组的复制，那么从底向上的自然归并最坏情况下需要访问8NlgN次数组。

最长子数组为k时：数组的最长子数组为k时，的最好情况是第一轮的所有子数组的长度均为k,设数组长度为N=K*2^m,那么归并树深库为m,每一层查找子数组需要进行2N次数组访问，每一层归并需要2N次数组访问完成复制到辅助数组的操作，需要2N次数组访问完成比较，需要2N次访问完成辅助数组到a数组的复制，那么从底向上的自然归并最坏情况下需要访问8Nlg(N/k)次数组操作。