2.2.23改进。用实验评估正文中所提到的归并排序的三项改进(请见练习2.2.11)的效果，并比较正文中实现的归并和练习2.2.10所实现的归并之间的性能。根据经验给出应该在何时为子数组切换到插入排序。

3)根据经验给出应该在何时为子数组切换到插入排序。

依据下图的试验结果，得出子数组长度在16至18时适合切换到插入排序。

public class E2d2d23d3

{

    public static double time (Double[] a,int subArrayLenTrunONInsertionSort)

    {

        Stopwatch timer =new Stopwatch();

        E2d2d11d3.sort(a,subArrayLenTrunONInsertionSort);

        return timer.elapsedTime();

    }

   

    public static double timeRandomInput(int N,int T,int subArrayLenTrunONInsertionSort)

    {

        double total =0.0;

        Double[] a=new Double[N];

        for (int t=0;t<T;t++)

        {

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

                a[i]=StdRandom.uniform();

            total+=time(a,subArrayLenTrunONInsertionSort);

        }

        return total/T;

    }//end timeRandomInput

   

    public static void main(String[] args)

    {

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

        int T=Integer.parseInt(args[1]);

        int maxInsertLen=Integer.parseInt(args[2]);

       

        StdOut.printf("For %d random Doubles %d times sort\n",N,T);

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

       {

        double t=timeRandomInput(N,T,i);

        StdOut.printf("subArrayLenTrunONInsertionSort=%d  spend time=%.2f\n",i,t);

       }

    }

}

public class E2d2d11d3

{

    public static void sort(Comparable[] a,int subArrayLenTrunONInsertionSort)

    {

        int len=a.length;

        Comparable[] aux=new Comparable[len];

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

            aux[i]=a[i];

        sort(a,aux,0,a.length-1,subArrayLenTrunONInsertionSort);

   }

    private static void sort(Comparable[] a,Comparable[] aux,int lo,int hi,int subArrayLenTrunONInsertionSort)

    {

        if ((hi-lo+1)<=subArrayLenTrunONInsertionSort)

        {

          insertionSort(a,lo,hi);

        }

        else

        {

          int mid=lo+(hi-lo)/2;

          sort(aux,a,lo,mid,subArrayLenTrunONInsertionSort);

          sort(aux,a,mid+1,hi,subArrayLenTrunONInsertionSort);

       

          if(!less(aux[mid+1],aux[mid]))

          {

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

                  a[i]=aux[i];

              return;

          }

         

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

        }

    }

   

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

    {

      int i=lo;

      int j=mid+1;

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

      {

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

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

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

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

      }

      }

    private static boolean less(Comparable v,Comparable w)

    { return v.compareTo(w)<0;}

   

    private static void exch(Comparable[] a,int i,int j)

    {

      Comparable t=a[i];

      a[i]=a[j];

      a[j]=t;

    }

   

    private static void insertionSort(Comparable[] a,int lo,int hi)

    {

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

        for (int j=i;j>lo && less(a[j],a[j-1]);j--)

            exch(a,j,j-1);

    }

   

 public static boolean isSorted(Comparable[] a)

    {

      for(int i=1;i<a.length;i++)

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

      return true;

    }

}