一：概念

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

----------------------------------------------------------------------------------------------------------------------

归并操作(merge)：也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。

归并操作的过程如下：

1. 申请空间S，使其大小为两个已经排序序列A、B之和，该空间用来存放合并A、B后的序列

2. 设定两个指针，最初位置分别为序列A、B的起始位置

3. 比较两个指针所指向的元素，选择相对较小的元素放入到空间S，并移动指针到下一个位置

4. 重复步骤3直到某一指针达到序列尾

5. 将另一序列剩下的所有元素直接复制到合并序列尾

----------------------------------------------------------------------------------------------------------------------

二：原理

分治法分以下三个步骤：

– Divide：划分问题转化(多个)为“简单”版的自己（子问题）。

– Conquer：使用相同的方法（通常是递归）解决每一个（子）问题

– Combine：结合的“简单”版本的结果，形成最终的解决方案。

归并排序可分以下三个步骤：

1. Sort the first half using merge sort. (recursive!)

2. Sort the second half using merge sort. (recursive!)

3. Merge the two sorted halves to obtain thefinal sorted array.

原理：把原始数组分成若干子数组,对每一个子数组进行排序,继续把子数组与子数组合并,合并后仍然有序,直到全部合并完,形成有序的数组

流程图：

三：特点

· Stable --稳定性

· O(n) extra space for arrays (as shown) --数组空间复杂度O(n)

· O(lg(n)) extra space for linked lists --链表空间复杂度O(lg(n))

· O(n·lg(n)) time --时间复杂度O(n*log(n))

· Not adaptive

· Does not require random access to data --不需要随机访问数据

四：JAVA如何实现归并排序

import java.util.Arrays;

public class MergeSort {

    public static void main(String[] args) {

        MergeSort t = new MergeSort();

        int[] arrays = {1,8,5,7,9,2,5};

        int[] a = t.mergeSort(arrays);

        System.out.println(Arrays.toString(a));

    }

    /**
     * @param array  其元素都是有效的整数（不为null）
     * @return 返回数组，数组按升序排序（低到高）
     */
    public int[] mergeSort(int array[])
    {
        // 如果数组元素有多个（大于1），则进行归并操作
        if(array.length > 1)
        {
            //初始化两个子数组的大小
            int elementsInA1 = array.length / 2;

            //子数组2的大小 = (array.length&1)==1? array.length/2 : array.length/2+1;
            //int elementsInA2 = array.length - elementsInA1; (同下)

            int elementsInA2 = (array.length&1)==1? elementsInA1+1 : elementsInA1;
           

            //声明和初始化两个子数组

            int arr1[] = new int[elementsInA1];
            int arr2[] = new int[elementsInA2];      

            //对两个子数组进行赋值
            arr1 = Arrays.copyOfRange(array, 0, elementsInA1);
            arr2 = Arrays.copyOfRange(array, elementsInA1,elementsInA1 + elementsInA2);

            //递归进行归并排序操作（递归函数调用）
            arr1 = mergeSort(arr1);
            arr2 = mergeSort(arr2);

            //-------------------------排序代码块【start】-------------------------------
            //定义三个变量
            // [i] -- 参数数组array的索引
            // [j] -- 子数组arr1中正在比较的元素的索引
            // [k] -- 子数组arr2中正在比较的元素的索引

            int i = 0, j = 0, k = 0;
            //下面的循环将一直运行，直到有一个子数组中的变空
            while(arr1.length != j && arr2.length != k){
                if(arr1[j] < arr2[k]){
                    //复制到最终的数组
                    array[i] = arr1[j];
                    i++;
                    j++;
                }else{
                    array[i] = arr2[k];
                    i++;
                    k++;
                }
            }

            //走到这，子数组中的一个已经被用尽，它已没有元素进行比较。这意味着剩下的数组中的元素
            //都是最高的（已排序），所以可以把它复制到最终的数组。
            while(arr1.length != j){
                array[i] = arr1[j];
                i++;
                j++;
            }

            while(arr2.length != k){
                array[i] = arr2[k];
                i++;
                k++;
            }
            //-------------------------排序代码块【end】-------------------------------
        }

        //返回已经排序的数组
        return array;
    }   

}