一、归并排序的定义：

归并排序是建立在归并操作上的一种有效的排序。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。分治，顾名思义，先分再治。
分在归并排序中就是将问题分解成最小的原子问题求解，并就是将各个原子问题的解合并。

二、归并排序的思想与实现：

2.1、思想：

举例说明，比如给定一个数组A = [5,2,6,1]

分割部分：
二分法分割数组，分成5、2 和 6、1 ， 5、2 又可以分成5和2， 6、1 又可以分成6和1。

分割
合并的过程，举例合并2、5 和 1、6 的过程

左指针2 和右指针1比较，1小，把1放入临时数组，right指针右移一位（图1到图2的过程）
左指针2 和右指针6比较， 2小，放入临时数组，left指针右移一位（图二到图三的过程）
左指针5 和右指针6比较，5小，放入临时数组，left指针已经到尾部，此时右移right指针到6（图三到图4的过程）
把6放入临时数组，至此，left和right指针均到尾部，合并完成（图四到图五的过程）

合并

2.2、java代码实现

归并排序的思想可以用递归来实现，把问题不断分解成子问题，然后把子问题的解合并的过程就是递归调用。通常在递归问题中，

首先我们需要重复执行的可递归的逻辑是什么：
本题中，我们是先分解数组，将数组分解成左数组和右数组，然后合并左数组和右数组。这个逻辑是可以重复递归执行的（通常可以用原子问题来验证）
我们需要搞清楚递归终止的条件是什么
在本题中，也就是数组分割到什么情况下不能再分割。数组分割我们需要不断根据数组的起始位置start和结束位置end来算出数组的中间位置middle是多少，直到数组的起始位置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);
}

完整的代码实现：

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];
        }

    }
}

三、归并排序的时间复杂度和应用

归并的时间复杂度：
归并排序的效率是比较高的，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(NlogN)。因为归并排序每次都是在相邻的数据中进行操作，所以归并排序在O(NlogN)的几种排序方法（快速排序，归并排序，希尔排序，堆排序）也是效率比较高的。
应用：
力扣面试题：合并两个升序数组
力扣912题：排序数组
《剑指 Offer》第 51 题：数组中的逆序对
力扣315题：计算右侧小于当前元素的个数
在实际项目中，通常用在比较大数据量的情况下可以使用到，比如对上G数据的排序。这个也可以从时间复杂度 nlogn 可以分析出来，常规的排序算法是O(n^2),当n越大时，logn 相比n^2的优势就会越大。

文末再附一个面试算法题：
给定两个允许有相同元素的升序数组，合并这两个数组到一个新数组中，当有多个相同元素时，清除这些元素，
要求不能使用 map 或者字典。例如 listA = [1,1,2,3,4,6]，listB = [3,5,6]，则合并后的数组为 [2,4,5,6]。
首先这个题目看到的时候，正常就是力扣上的一个题目：合并两个升序数组。
但是也有不同之处，就是升序之后我们要去除重复的元素。整体上就是先合并两个升序数组，然后再清除重复的元素。
合并升序数组的思路：
因为两个数组都是有序的，所以两个数组内之间的元素就不用再排序了，我们至需要比较这两个数组内的元素大小。举例说明：A数组中的1 和 B数组中的3 比较，哪个数组小，就移动哪个数组下标位置，1 < 3, 则A数组下标移动，继续比较A数组中下一个 1 < 3, 再比较 2<3 ,再比较 3= 3，继续移动A数组指针，4 > 3, 此时移动B数组下标到 5， 4<5 ....以此类推。我们在每次比较的过程中将小的数组元素放入到一个新的数组中，这样就完成了合并两个升序数组。

    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数组和B数组均未遍历到尾部
                if (A[acur] <= B[bcur]) {
                    result[acur + bcur] = A[acur];
                    acur++;
                } else{
                    result[acur + bcur] = B[acur];
                    bcur++;
                }
            } else if (bcur < n) {
                //A数组遍历到尾部了
                result[acur+bcur] = B[bcur];
                bcur++;
            } else if (acur < m) {
                result[acur+bcur] = A[acur];
                acur++;
                //B数组遍历到尾部
            }
        }
    }

去除重复元素的思路：
首先合并后的数组是升序的，所以重复元素是相邻的。我们只需要比较相邻的两个元素，如果相同，则遍历这个数组，从相同元素下标开始遍历，找到所有相同元素，数组元素值置为0。再继续比较相邻元素，相同再遍历数组，元素值置为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]);
            }
        }

另一种思路：
上面的思路是我们先合并数组，然后再去除重复元素，正常来说我们也可以在合并数组的过程判断元素有没有重复，有重复，不放到新数组中就可以，但是题目又要求我们不能使用map或者字典，那么我们有没有什么方式在不用map或者字典的前提下，判断元素存不存在呢？有的，位图就可以做到，此处不再赘述...