**归并排序**(Merge Sort )是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法的一个非常典型的应用。l

算法思路

• 把长度为n的输入序列分成两个长度为n/2的子序列;
• 对这两个子序列分别采用归并排序;
• 将两个排序好的子序列合并成一个最终的排序序列。
• 

分阶段，可以理解为就是递归拆分子序列的过程，递归深度为log2n。
治阶段，我们需要将两个已经有序的子序列合并成一个有序序列

如何将两个已经有序的子序列合并成一个有序的序列，我们需要借助一个临时数组temp。那么以(29,38,65,87)和{23,27,72,78}两个子序列为例，进行合并。

设置2个指针i和j,初始i指向第1个子集的开头，j指向第2个子集的开头，然后比较2个元素，将最小的值放入temp数组，放入哪个子集的数据，就向后移动哪个子集的指针。

谁放进了temp里面谁++

第一趟:比较i位置和j位置的元素，将最小值23填入temp数组中，同时j++。
第二趟:比较i位置和j位置的元素，将最小值27填入temp数组中，同时j++。

代码实现

public class MergeSort{
    public static void main(String[] args){
        int [ ]arr = {8,4,5,7,1,3,6,2};
        mergesort(arr, e,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    public statuc void mergeSort(int[] arr,int low ,int high)
    {
        if(low<high)
        {
            int mid = (low + high)/2;
            //对左边进行归并排序
            mergeSort(arr,low,mid);
            //对右边进行归并排序
            mergeSort(arr,mid+1,heigh);
            //合并
            merge()
        }
    }
    public static void merge(int[] arr, int low, int mid, int high)
    {
        //创建1个临时数组
        int[] temp = new int[arr.length];
        int i = low;
        int j = mid+1;
        while(i<=mid && j<=high)
        {
            if(arr[i]<=arr[j])
            {
                temp[k++] = arr[i++];
            }else{
                 temp[k++] = arr[j++];
            }
        }
        //如果左边有剩余
        while(i<=mid)
        {
            temp[k++] = arr[i++];
        }
        //若果右边有剩余
        while(i<=mid)
        {
            temp[k++] = arr[j++];
        }
           k=0;
        while(low<=high)
        {
            arr[low++] = temp[k++];
        }
    }
}

算法稳定性：

如果待排序的序列中存在两个或两个以上具有相同关键词的数据，排序后这些数据的相对次序保持不变，通俗地讲，就是两个相同的数的相对顺序不会发生改变，则该算法是稳定的:归并排序是稳定的排序算法。

时间复杂度:

O(nlog2n)