归并排序

将一个需要排序的数组先把它从中间一分为而，然后在对每个子数组递归排序，然后将两个排序好的数组合二为一

//归并排序的时间复杂度是O（nlogn）
public static void mergeSort(int [] a){
        if(a.length>1){//递归的退出条件
          //将原来的数组分为b,c
            int [] b = new int[a.length/2];
            int [] c = new int[a.length-b.length];
            int index = 0;
            for (int i = 0;i<a.length;i++){
                if(i<b.length)
                    b[i] = a[i];
                else
                    c[index++] = a[i];
            }
          //递归的将子数组b,c排序
            mergeSort(b);
            mergeSort(c);
          //将排序好的b,c合并到a数组
            merge(b,c,a);
        }

    }

    //合并两个数组到原数组，数组b,c是a的子数组
    public static void merge(int [] b,int [] c,int [] a){
        int i = 0;//b数组的下标
        int j = 0;//c数组的下标
        int k = 0;//a数组的下标
        int p = b.length;
        int q = c.length;
        while(i<p&&j<q){//次循环的目的是将b数组和c数组中小的值放入a数组，直到一个数组中的元素全部放入a数组中
            if(b[i]<=c[j]){
                a[k++] = b[i++];
            }else{
                a[k++] = c[j++];
            }
        }

      //将b或c数组中剩余的元素放入数组a当中
        if(i==p){
            for(;j<q;j++){
                a[k++] = c[j];
            }
        }else{
            for(;i<p;i++){
                a[k++] = b[i];
            }
        }
    }