归并排序

public class Test {
    public static void main(String[] args) {
        int arr1[]={1,3,5,7,9};
        int arr2[]={2,4,6,8,10};
        memeryArray(arr1, arr2);
    }
    
    public static void memeryArray(int arr1[],int arr2[]){
        int i=0,j = 0,k = 0;
        int arr3[]=new int[arr1.length+arr2.length];
        while(i<arr1.length&&j<arr2.length){
            if(arr1[i]<arr2[j])
                arr3[k++]=arr1[i++];
            else
                arr3[k++]=arr2[j++];
        }
        while(i<arr1.length)
            arr3[k++]=arr1[i++];
        while(j<arr2.length)
            arr3[k++]=arr2[j++];
        for (int i1 = 0; i1 < arr3.length; i1++) {
            System.out.println(arr3[i1]);
        }
    }
}

上面就是对两个有序数组进行归并排序时间复杂度是常数级，所以值得借鉴。于是产生了更加牛逼的归并排序。可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。

public class MergeSort {
    ////将有二个有序数列a[first...mid]和a[mid...last]合并。
    void mergearray(int a[], int first, int mid, int last, int temp[])
    {
        int i = first, j = mid + 1;
        int m = mid,   n = last;
        int k = 0;
        
        while (i <= m && j <= n)
        {
            if (a[i] <= a[j])
                temp[k++] = a[i++];
            else
                temp[k++] = a[j++];
        }
        
        while (i <= m)
            temp[k++] = a[i++];
        
        while (j <= n)
            temp[k++] = a[j++];
        //将合并序列复制到原始序列中
        for (i = 0; i < k; i++)
            a[first + i] = temp[i];
    }
    
    void mergesort(int a[], int first, int last, int temp[])
    {
        if (first < last)
        {
            int mid = (first + last) / 2;
            mergesort(a, first, mid, temp);    //左边有序
            mergesort(a, mid + 1, last, temp); //右边有序
            mergearray(a, first, mid, last, temp); //再将二个有序数列合并
        }
    }
}

public class Test {
    public static void main(String[] args){
        int arr[]={1,4,2,54,3,0,9};
        int temp[]=new int[arr.length];
        MergeSort merge=new MergeSort();
        merge.mergesort(arr, 0, arr.length-1, temp);
        for (int i = 0; i < temp.length; i++) {
            System.out.print(temp[i]+" ");
        }
    }
}

归并排序与初始序列无关，时间复杂度位

平均是O（n㏒2n） 最好O（n㏒2n） 最坏O（n㏒2n）

空间复杂度O（n）