## **歸并排序** 歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為2-路歸并。 ## **算法描述** 兩種方法 * 遞歸法（Top-down） 1. 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列 2. 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置 3. 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置 4. 重復步驟3直到某一指針到達序列尾 5. 將另一序列剩下的所有元素直接復制到合并序列尾 * 迭代法（Bottom-up） 原理如下（假設序列共有n個元素）： 1. 將序列每相鄰兩個數字進行歸并操作，形成ceil(n/2)個序列，排序后每個序列包含兩/一個元素 2. 若此時序列數不是1個則將上述序列再次歸并，形成ceil(n/4)個序列，每個序列包含四/三個元素 3. 重復步驟2，直到所有元素排序完畢，即序列數為1 ## **穩定性** 因為我們在遇到相等的數據的時候必然是按順序“抄寫”到輔助數組上的，所以，歸并排序同樣是穩定算法。 ## **適用場景** 歸并排序在數據量比較大的時候也有較為出色的表現（效率上），但是，其空間復雜度O(n)使得在數據量特別大的時候（例如，1千萬數據）幾乎不可接受。而且，考慮到有的機器內存本身就比較小，因此，采用歸并排序一定要注意。 ## **JAVA代碼實現** ``` public static void mergeSort(int[] arr){ int[] temp =new int[arr.length]; internalMergeSort(arr, temp, 0, arr.length-1); } private static void internalMergeSort(int[] arr, int[] temp, int left, int right){ //當left==right的時，已經不需要再劃分了 if (left<right){ int middle = (left+right)/2; internalMergeSort(arr, temp, left, middle); //左子數組 internalMergeSort(arr, temp, middle+1, right); //右子數組 mergeSortedArray(arr, temp, left, middle, right); //合并兩個子數組 } } // 合并兩個有序子序列 private static void mergeSortedArray(int arr[], int temp[], int left, int middle, int right){ int i=left; int j=middle+1; int k=0; while (i<=middle && j<=right){ temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++]; } while (i <=middle){ temp[k++] = arr[i++]; } while ( j<=right){ temp[k++] = arr[j++]; } //把數據復制回原數組 for (i=0; i<k; ++i){ arr[left+i] = temp[i]; } } ```