1.简介

归并排序：是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

归并操作(Merge)：也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。归并排序有多路归并排序、两路归并排序 , 可用于内排序，也可以用于外排序。这里仅对内排序的两路归并方法进行讨论。

2.图解

在这里插入图片描述

3.算法思想

归并排序有两种实现方式：基于递归的归并排序和基于循环的归并排序。（也叫自顶向下的归并排序和自底向上的归并排序）
两种实现对于最小集合的归并操作思想是一样的区别在于如何划分数组
分治法将问题分(divide) 成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之。

4.Java递归实现

package com.lsl.datastructure;
public class MergeSort { 
    public static void main(String[] args) { 
        int[] nums = {  5,6,3,1,8,7,2,4};
        sort(nums);
        for (int num : nums) { 
            System.out.print(num+" ");
        }
    }
    /** * @param arr 待排序数组 */
    public static void sort(int[] arr){ 
        //在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        int [] temp = new int[arr.length];
        mergeSort(arr,0,arr.length-1,temp);
    }
    /** * @param arr 待排序数组 * @param left 起始元素角标 0 * @param right 最后一个元素角标 n -1 * @param temp 临时数组 */
    private static void mergeSort(int[] arr, int left, int right,int[] temp) { 
        //2.递归划分数组
        if (left<right) { 
            //1.开始归并排序 向下取整
            int mid = (left + right) / 2;
            //左边归并排序，使得左子序列有序
            mergeSort(arr, left, mid,temp);
            //右边归并排序，使得右子序列有序
            mergeSort(arr, mid + 1, right,temp);
            //3.将两边的元素归并排序
            merge(arr, left, mid, right,temp);
        }
    }
    /** * @param arr 待排序数组 * @param left 分段后的起始元素角标 * @param right 分段后的最后一个元素角标 * @param temp 临时数组 */
    private static void merge(int[] arr, int left, int mid, int right,int[] temp) { 
        //左序列指针
        int i = left;
        //右序列指针
        int j = mid + 1;
        //临时数组指针
        int t = 0;
        while (i<=mid && j<=right){ 
            if(arr[i]<=arr[j]){ 
                temp[t++] = arr[i++];
            }else { 
                temp[t++] = arr[j++];
            }
        }
        //将左边剩余元素填充进temp中
        while(i<=mid){ 
            temp[t++] = arr[i++];
        }
        //将右序列剩余元素填充进temp中
        while(j<=right){ 
            temp[t++] = arr[j++];
        }
        t = 0;
        //将temp中的元素全部拷贝到原数组中
        while(left <= right){ 
            arr[left++] = temp[t++];
        }
    }
}

5.算法分析：

（1）稳定性
　归并排序是一种稳定的排序。

（2）存储结构要求
　可用顺序存储结构。也易于在链表上实现。

（3）时间复杂度
　对长度为n的文件，需进行趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。

（4）空间复杂度
　需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)

6.总结

归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从本文可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)