概述
歸併（Merge）排序法是將兩個（或兩個以上）有序表合併成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然後再把有序子序列合併為整體有序序列。
歸併排序採用的是遞歸來實現，屬於“分而治之”，將目標數組從中間一分為二，之後分別對這兩個數組進行排序，排序完畢之後再將排好序的兩個數組“歸併”到一起，歸併排序最重要的也就是這個“歸併”的過程，歸併的過程中需要額外的跟需要歸併的兩個數組長度一致的空間。
效果圖：
步驟
申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合併後的序列設定兩個指針，最初位置分別為兩個已經排序序列的起始位置比較兩個指針所指向的元素，選擇相對小的元素放入到合併空間，並移動指針到下一位置重複步驟3直到某一指針達到序列尾將另一序列剩下的所有元素直接複製到合併序列尾實例
原始數據：
3 5 2 6 2
歸併的前提是將數組分開，一分為二，再一分為二，分到不能再分，進行歸併。
第一輪分隔，索引2 ((0+4)/2=2) 為中間
[3 5 2] [6 2]
第二輪分隔，對[3 5 2]進行分隔
[3 5] [2] [6 2]
第三輪分隔，對[3 5]進行分隔
[3] [5] [2] [6 2]
合併[3] [5]
[3 5] [2] [6 2]
合併[3 5] [2]
[2 3 5] [6 2]
第四輪分隔，對[6 2]進行分隔
[2 3 5] [6] [2]
合併[6] [2]
[2 3 5] [2 6]
合併[2 3 5] [2 6]
[2 2 3 5 6]
代碼實現(Java)
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("正在進行第" + mark + "次分隔，得到"); System.out.println("[" + low + "-" + mid + "] [" + (mid + 1) + "-" + high + "]"); // 左邊數組sort(array, low, mid); // 右邊數組sort(array, mid + 1, high); // 左右歸併merge(array, low, mid, high); } return array; } /** * 對數組進行歸併* * @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; // 把較小的數先移到新數組中while (i <= mid && j <= high) { if (array[i] < array[j]) { temp[k++] = array[i++]; } else { temp[k++] = array[j++]; } } // 兩個數組之一可能存在剩餘的元素// 把左邊剩餘的數移入數組while (i <= mid) { temp[k++] = array[i++]; } // 把右邊邊剩餘的數移入數組while (j <= high) { temp[k++] = array[j++]; } // 把新數組中的數覆蓋array數組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("最終結果"); for (int i : sorted) { System.out.print(i + " "); } }}測試輸出結果：
正在進行第1次分隔，得到[0-2] [3-4]正在進行第2次分隔，得到[0-1] [2-2]正在進行第3次分隔，得到[0-0] [1-1]合併:[0-0] 和[1-1]合併:[0-1] 和[2-2]正在進行第4次分隔，得到[3-3] [4-4]合併:[3-3] 和[4-4]合併:[0-2] 和[3-4]最終結果2 2 3 5 6
經測試，與實例中結果一致。