## **归并排序** 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为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]; } } ```