摘要：概述歸并排序法是將兩個(gè)或兩個(gè)以上有序表合并成一個(gè)新的有序表，即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的。

歸并（Merge）排序法是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表，即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列。

歸并排序采用的是遞歸來實(shí)現(xiàn)，屬于“分而治之”，將目標(biāo)數(shù)組從中間一分為二，之后分別對(duì)這兩個(gè)數(shù)組進(jìn)行排序，排序完畢之后再將排好序的兩個(gè)數(shù)組“歸并”到一起，歸并排序最重要的也就是這個(gè)“歸并”的過程，歸并的過程中需要額外的跟需要?dú)w并的兩個(gè)數(shù)組長度一致的空間。

效果圖：

申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列

設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置

比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置

重復(fù)步驟3直到某一指針達(dá)到序列尾

將另一序列剩下的所有元素直接復(fù)制到合并序列尾

原始數(shù)據(jù)：

3 5 2 6 2

歸并的前提是將數(shù)組分開，一分為二，再一分為二，分到不能再分，進(jìn)行歸并。

第一輪分隔，索引2 ((0+4)/2=2) 為中間

[3 5 2] [6 2]

第二輪分隔，對(duì)[3 5 2]進(jìn)行分隔

[3 5] [2] [6 2]

第三輪分隔，對(duì)[3 5]進(jìn)行分隔

[3] [5] [2] [6 2]

合并[3] [5]

[3 5] [2] [6 2]

合并[3 5] [2]

[2 3 5] [6 2]

第四輪分隔，對(duì)[6 2]進(jìn)行分隔

[2 3 5] [6] [2]

合并[6] [2]

[2 3 5] [2 6]

合并[2 3 5] [2 6]

[2 2 3 5 6]

package com.coder4j.main.arithmetic.sorting;

public class Merge {
    
    private static int mark = 0;

    /**
     * 歸并排序
     * 
     * @param array
     * @param low
     * @param high
     * @return
     */
    private static int[] sort(int[] array, int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
            mark++;
            System.out.println("正在進(jìn)行第" + mark + "次分隔，得到");
            System.out.println("[" + low + "-" + mid + "] [" + (mid + 1) + "-" + high + "]");
            // 左邊數(shù)組
            sort(array, low, mid);
            // 右邊數(shù)組
            sort(array, mid + 1, high);
            // 左右歸并
            merge(array, low, mid, high);
        }
        return array;
    }

    /**
     * 對(duì)數(shù)組進(jìn)行歸并
     * 
     * @param array
     * @param low
     * @param mid
     * @param high
     */
    private static void merge(int[] array, int low, int mid, int high) {
        System.out.println("合并:[" + low + "-" + mid + "] 和 [" + (mid + 1) + "-" + high + "]");
        int[] temp = new int[high - low + 1];
        int i = low;// 左指針
        int j = mid + 1;// 右指針
        int k = 0;
        // 把較小的數(shù)先移到新數(shù)組中
        while (i <= mid && j <= high) {
            if (array[i] < array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }
        // 兩個(gè)數(shù)組之一可能存在剩余的元素
        // 把左邊剩余的數(shù)移入數(shù)組
        while (i <= mid) {
            temp[k++] = array[i++];
        }
        // 把右邊邊剩余的數(shù)移入數(shù)組
        while (j <= high) {
            temp[k++] = array[j++];
        }
        // 把新數(shù)組中的數(shù)覆蓋array數(shù)組
        for (int m = 0; m < temp.length; m++) {
            array[m + low] = temp[m];
        }
    }

    /**
     * 歸并排序
     * 
     * @param array
     * @return
     */
    public static int[] sort(int[] array) {
        return sort(array, 0, array.length - 1);
    }

    public static void main(String[] args) {
        int[] array = { 3, 5, 2, 6, 2 };
        int[] sorted = sort(array);
        System.out.println("最終結(jié)果");
        for (int i : sorted) {
            System.out.print(i + " ");
        }
    }
}

測試輸出結(jié)果：

正在進(jìn)行第1次分隔，得到
[0-2] [3-4]
正在進(jìn)行第2次分隔，得到
[0-1] [2-2]
正在進(jìn)行第3次分隔，得到
[0-0] [1-1]
合并:[0-0] 和 [1-1]
合并:[0-1] 和 [2-2]
正在進(jìn)行第4次分隔，得到
[3-3] [4-4]
合并:[3-3] 和 [4-4]
合并:[0-2] 和 [3-4]
最終結(jié)果
2 2 3 5 6 

經(jīng)測試，與實(shí)例中結(jié)果一致。