一箕慧、歸并排序的定義：

歸并排序是建立在歸并操作上的一種有效的排序歉胶。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用婿斥。分治劝篷，顧名思義，先分再治民宿。
分在歸并排序中就是將問題分解成最小的原子問題求解娇妓，并就是將各個(gè)原子問題的解合并。

二活鹰、歸并排序的思想與實(shí)現(xiàn)：

2.1哈恰、思想：

舉例說明只估，比如給定一個(gè)數(shù)組A = [5,2,6,1]

分割部分：
二分法分割數(shù)組，分成5着绷、2 和 6蛔钙、1 ， 5荠医、2 又可以分成5和2吁脱， 6、1 又可以分成6和1彬向。

分割
合并的過程兼贡，舉例合并2、5 和 1娃胆、6 的過程

左指針2 和右指針1比較遍希，1小，把1放入臨時(shí)數(shù)組里烦，right指針右移一位（圖1到圖2的過程）
左指針2 和右指針6比較孵班， 2小，放入臨時(shí)數(shù)組招驴，left指針右移一位（圖二到圖三的過程）
左指針5 和右指針6比較篙程，5小，放入臨時(shí)數(shù)組别厘，left指針已經(jīng)到尾部虱饿，此時(shí)右移right指針到6（圖三到圖4的過程）
把6放入臨時(shí)數(shù)組，至此触趴，left和right指針均到尾部氮发，合并完成（圖四到圖五的過程）

合并

2.2、java代碼實(shí)現(xiàn)

歸并排序的思想可以用遞歸來實(shí)現(xiàn)冗懦，把問題不斷分解成子問題爽冕，然后把子問題的解合并的過程就是遞歸調(diào)用。通常在遞歸問題中披蕉，

首先我們需要重復(fù)執(zhí)行的可遞歸的邏輯是什么：
本題中颈畸，我們是先分解數(shù)組，將數(shù)組分解成左數(shù)組和右數(shù)組没讲，然后合并左數(shù)組和右數(shù)組眯娱。這個(gè)邏輯是可以重復(fù)遞歸執(zhí)行的（通常可以用原子問題來驗(yàn)證）
我們需要搞清楚遞歸終止的條件是什么
在本題中爬凑，也就是數(shù)組分割到什么情況下不能再分割徙缴。數(shù)組分割我們需要不斷根據(jù)數(shù)組的起始位置start和結(jié)束位置end來算出數(shù)組的中間位置middle是多少，直到數(shù)組的起始位置start>=middle,即遞歸終止嘁信。
大致的偽代碼

sort(start,end,nums){
    if(start >= middle){
        return;
    }
    middle = (start + end)/2;
    sort(start,middle,nums);
    sort(middle+1,end,nums);
    mergeSort(start,middle,end,nums);
}

完整的代碼實(shí)現(xiàn)：

class Solution {
    public int[] sortArray(int[] nums) {
        int[] temp = new int[nums.length];
        mergeSort(0,nums.length-1,nums);
        return nums;
    }

    /**
     * @param start
     * @param end
     * @param nums
     * @return
     */
    private void mergeSort(int start, int end, int[] nums) {
        if (start >= end) {
            return;
        }
        int mid = (start + end)/2;
        mergeSort(start,mid,nums);
        mergeSort(mid+1,end,nums);
        mergeArray(start,mid, end,nums);
    }

    private void mergeArray(int start, int mid, int end, int[] nums) {
        int p1 = start;
        int p2 = mid+1;
        int p=0;

        int[] temp = new int[end-start+1];
        while (p1 <= mid && p2 <= end) {
            if (nums[p1] >= nums[p2]) {
                temp[p++] = nums[p2++];
            } else {
                temp[p++] = nums[p1++];
            }
        }
        while (p2 <= end) {
            temp[p++] = nums[p2++];
        }
        while (p1 <= mid) {
            temp[p++] = nums[p1++];
        }
        for (int i = 0; i < temp.length; i++) {
            nums[i + start] = temp[i];
        }

    }
}

三于样、歸并排序的時(shí)間復(fù)雜度和應(yīng)用

歸并的時(shí)間復(fù)雜度：
歸并排序的效率是比較高的疏叨，設(shè)數(shù)列長為N，將數(shù)列分開成小數(shù)列一共要logN步穿剖，每步都是一個(gè)合并有序數(shù)列的過程蚤蔓，時(shí)間復(fù)雜度可以記為O(N)，故一共為O(NlogN)携御。因?yàn)闅w并排序每次都是在相鄰的數(shù)據(jù)中進(jìn)行操作，所以歸并排序在O(NlogN)的幾種排序方法（快速排序既绕，歸并排序啄刹，希爾排序，堆排序）也是效率比較高的凄贩。
應(yīng)用：
力扣面試題：合并兩個(gè)升序數(shù)組
力扣912題：排序數(shù)組
《劍指 Offer》第 51 題：數(shù)組中的逆序?qū)?/a>
力扣315題：計(jì)算右側(cè)小于當(dāng)前元素的個(gè)數(shù)
在實(shí)際項(xiàng)目中誓军，通常用在比較大數(shù)據(jù)量的情況下可以使用到，比如對上G數(shù)據(jù)的排序疲扎。這個(gè)也可以從時(shí)間復(fù)雜度 nlogn 可以分析出來昵时，常規(guī)的排序算法是O(n^2),當(dāng)n越大時(shí)，logn 相比n^2的優(yōu)勢就會(huì)越大椒丧。

文末再附一個(gè)面試算法題：
給定兩個(gè)允許有相同元素的升序數(shù)組壹甥，合并這兩個(gè)數(shù)組到一個(gè)新數(shù)組中，當(dāng)有多個(gè)相同元素時(shí)壶熏，清除這些元素句柠，
要求不能使用 map 或者字典。例如 listA = [1,1,2,3,4,6]棒假，listB = [3,5,6]溯职，則合并后的數(shù)組為 [2,4,5,6]。
首先這個(gè)題目看到的時(shí)候帽哑，正常就是力扣上的一個(gè)題目：合并兩個(gè)升序數(shù)組谜酒。
但是也有不同之處，就是升序之后我們要去除重復(fù)的元素妻枕。整體上就是先合并兩個(gè)升序數(shù)組僻族，然后再清除重復(fù)的元素。
合并升序數(shù)組的思路：
因?yàn)閮蓚€(gè)數(shù)組都是有序的屡谐，所以兩個(gè)數(shù)組內(nèi)之間的元素就不用再排序了鹰贵，我們至需要比較這兩個(gè)數(shù)組內(nèi)的元素大小。舉例說明：A數(shù)組中的1 和 B數(shù)組中的3 比較康嘉，哪個(gè)數(shù)組小碉输，就移動(dòng)哪個(gè)數(shù)組下標(biāo)位置，1 < 3, 則A數(shù)組下標(biāo)移動(dòng)亭珍，繼續(xù)比較A數(shù)組中下一個(gè) 1 < 3, 再比較 2<3 ,再比較 3= 3敷钾，繼續(xù)移動(dòng)A數(shù)組指針枝哄，4 > 3, 此時(shí)移動(dòng)B數(shù)組下標(biāo)到 5， 4<5 ....以此類推阻荒。我們在每次比較的過程中將小的數(shù)組元素放入到一個(gè)新的數(shù)組中挠锥，這樣就完成了合并兩個(gè)升序數(shù)組。

    public void merge(int[] A, int m, int[] B, int n) {
        int [] result = new int[m+n];
        int acur = 0;
        int bcur = 0;
        while(acur < m || bcur < n){
            if (acur < m && bcur < n) {
                //A數(shù)組和B數(shù)組均未遍歷到尾部
                if (A[acur] <= B[bcur]) {
                    result[acur + bcur] = A[acur];
                    acur++;
                } else{
                    result[acur + bcur] = B[acur];
                    bcur++;
                }
            } else if (bcur < n) {
                //A數(shù)組遍歷到尾部了
                result[acur+bcur] = B[bcur];
                bcur++;
            } else if (acur < m) {
                result[acur+bcur] = A[acur];
                acur++;
                //B數(shù)組遍歷到尾部
            }
        }
    }

去除重復(fù)元素的思路：
首先合并后的數(shù)組是升序的侨赡，所以重復(fù)元素是相鄰的蓖租。我們只需要比較相鄰的兩個(gè)元素，如果相同羊壹，則遍歷這個(gè)數(shù)組蓖宦，從相同元素下標(biāo)開始遍歷，找到所有相同元素油猫，數(shù)組元素值置為0稠茂。再繼續(xù)比較相鄰元素，相同再遍歷數(shù)組情妖，元素值置為0睬关，依次類推。

int[] result = {1,1,2,2,2,3,5,6,6};
        int left = 0;
        int right = 1;

        int[] noRepeatResult = new int[result.length];
        // 1,1,2,2,2,3,5,6,6
        while (right < result.length) {
            if (result[left] == result[right]) {
                int x = result[left];
                int count = 0;
                for (int i = left; i < result.length; i++) {
                    if (result[i] == x) {
                        result[i] = 0;
                        count++;
                    } else {
                        break;
                    }
                }
                left += count;
                right = left + 1;
            } else {
                left++;
                right++;
            }
        }
        List<Integer> a = new ArrayList<>();
        for (int i=0;i<result.length;i++) {
            if (result[i] != 0) {
                a.add(result[i]);
            }
        }

另一種思路：
上面的思路是我們先合并數(shù)組毡证，然后再去除重復(fù)元素电爹，正常來說我們也可以在合并數(shù)組的過程判斷元素有沒有重復(fù)，有重復(fù)料睛，不放到新數(shù)組中就可以藐不，但是題目又要求我們不能使用map或者字典，那么我們有沒有什么方式在不用map或者字典的前提下秦效，判斷元素存不存在呢雏蛮？有的，位圖就可以做到阱州，此處不再贅述...