归并排序，采用分治思想，将已经排好序的两个数组合并成一个有序的数组，时间复杂度是O(nlogn)，也是一种稳定的排序算法，其基本流程如下：
采用分治的思想，假设有一个局部已经排好序的数组Y = {-4, -1, 1, 2, 5, -3, -2, 0, 3, 4}，则可以分成两个组 A = {-4, -1, 1, 2, 5} 和 B = {-3, -2, 0, 3, 4}，现需要将他们合并在一起，则只需要用两个下标遍历两个数组，从 A[0], B[0] 开始对比，小的 (A[0])先放入目标数组，然后遍历A数组的下标加1，直到其中一个数组被遍历完全，剩下数组的剩余数可直接加到目标数组之后：
A = {-4, -1, 1, 2, 5} ， B = {-3, -2, 0, 3, 4} ，目标数组 C = {} 新开一个数组C，比较 A[0], B[0]，A[0] < B[0]，将 A[0] 放入C中，并将遍历A数组的下标往右移动，再比较A[1]，B[0]，将 B[0]放入目标数组C，B下标加1，一直循环直到有一数组被遍历完全(此例为 B 数组)，则把另一数组之后的数直接加到C之后得：C = {-4，-3，-2，-1，0，1，2，3，4，5}，C有序了之后将C的内容拷贝到原来数组 Y 中，则 Y 最后变为有序数组
归并排序正是一个一个这样的小过程堆起来得到最后的目标数组：
初始数组为 1, -1, 2, 5, -4, 0, -2, -3, 3, 4，首先分组，要一直分到所有的组内都是有序的为止(其实就是分成每个组中只有一个元素，因为一个元素肯定是有序的)，然后将组两个两个按上述方法合并就可以了：
第一次分组： { {1, -1, 2, 5, -4} , {0, -2, -3, 3, 4} }第二次分组： { { {1, -1} , {2, 5, -4} } , { {0, -2} , {-3, 3, 4} } }第三次分组： { { { {1} , {-1} } , { {2} , {5, -4} } } , { { {0} , {-2} } , { {-3} , {3, 4} } } }第四次分组： { { { {1} , {-1} } , { {2} , { {5} , {-4} } } } , { { {0} , {-2} } , { {-3} , { {3} , {4} } } } } 至此，所有的组内都是有序的了(组内元素个数都为1)，因此可以开始合并同组成员，合并依据是只合并同组成员，并且是从小组慢慢合并到大组： 分组情况： { { { {1} , {-1} } , { {2} , { {5} , {-4} } } } , { { {0} , {-2} } , { {-3} , { {3} , {4} } } } }第一次合并：（ 1 与 -1 合并，5 与 -4 合并，0 与 -2 合并，3 与 4 合并） { { { -1 , 1 } , { {2} , { -4, 5 } } } , { { -2 , 0 } , { {-3} , { 3 , 4 } } } }第二次合并：（ 2 与 {-4，5} 合并，-3 与 {3，4} 合并） { { { -1 , 1 } , { -4 , 2 , 5 } } , { { -2 , 0 } , { -3 , 3 , 4 } } }第三次合并：（{-1，1} 与 {-4，2，5} 合并，{-2，0} 与 {-3，3，4} 合并） { { -4 , -1 , 1 , 2 , 5 } , { -3 , -2 , 0 , 3 , 4 } }第四次合并：（ { -4 , -1 , 1 , 2 , 5 } 和 { -3 , -2 , 0 , 3 , 4 } 合并，即最上面举例的合并过程） {-4 , -3 , -2 , -1 , 0 , 1 , 2 , 3 , 4 , 5} 排序完毕不难看出，将一个大问题划分成若干个小问题解决，然后从小问题开始一步一步向大问题靠近并解决，这便是分治的思想。上述分组之后合并的过程是从最内部的组开始的，是一个递归返回的过程，而分组是递归的过程，因此会用递归来实现归并排序(当然也可以用非递归)：
/** * 将两个有序数组合成一个有序数组，值得注意的是， * 这里说的 "两个有序数组" 指的是分成的两个组， * 并不是真正的两个数组，它们本质还是在一个完整的、 * 最初的那个数组里面，并且这两个部分一定是连续的 * 所以可以这么说： * 将大数组中的两个有序的部分合并成一个部分 * @param nums 需要排序的数组 (最初的整个数组) * @param left 需要合并的第一部分的左边界下标 * @param m 需要合并的第二部分的左边界下标，减 1 为需要合并的第一部分的右边界下标 * @param right 需要合并的第二部分的右边界下标 */ void mergeUp(int nums[], int left, int m, int right) { /** * 可以开辟新的数组作为合并之后的数组， * 然后再拷贝回原数组，也可以开辟两个数组， * 作为要合并的两个部分的新数组，这里采用的是 * 第二种方法 */ int lSize = m - left; // 第一部分的数组长度 int rSize = right - m + 1; // 第二部分的数组长度 int lNums[lSize], rNums[rSize]; // 开辟两个数组 (为了方便就不动态开辟了，但最好还是动态开辟) /** * i j k 是三个索引下标 * i 是数组第一部分的下标，后续还作为新开辟的左边数组的下标 * j 是数组第二部分的下标，后续作为新开辟的右边数组的下标 * k 初始作为两个新数组下标的索引，后续是这两个连续部分在原数组中的下标 */ int i, j, k = 0; /** * 分别将第一第二部分的数存储在新开辟的左右两个数组中 * 第一部分起始下标为 left，终止下标为 m - 1 * 第二部分起始下标为 m，终止下标为 right * 对于两个新开辟的数组，其下标都是从 0 开始 */ for(i = left; i < m; ++i) lNums[k++] = nums[i]; k = 0; for(j = m; j <= right; ++j) rNums[k++] = nums[j]; /** * 新数组下标从 0 开始，两个连续部分是从最左边界 left 开始的 */ i = 0, j = 0, k = left; /** * 将两个有序数组合并成一个有序数组，合并的位置是原来数组的 * 两个部分所在的位置，即 从 nums[left] ~ nums[right] * 一直合并直到有一个数组遍历完全 */ while(i<lSize && j<rSize) { if(lNums[i] < rNums[j]) nums[k++] = lNums[i++]; else nums[k++] = rNums[j++]; } /** * 将未遍历完全的数组的剩余的数直接加到原数组对应的位置 * 还是以 k 作为索引 */ while(i < lSize) nums[k++] = lNums[i++]; while(j < rSize) nums[k++] = rNums[j++]; } /** * 采用递归将大数组拆分为有序数组 * @param left 数组的左边界下标 * @param right 数组的右边界下标 */ void mergeUpSort(int nums[], int left, int right) { /** * 递归出口，当数组左边界等于右边界时， * 说明此时这个子数组只有一个元素， * 即这个子数组是有序的，不用再切分了， * 直接返回 */ if(left == right) return; /** * 每次将一个组分成两个小组，以这个组 * 的 left 作为左边界下标，m 作为第一个小 * 组的右边界下标，以 m+1 作为第二个小组的 * 左边界下标，right 作为第二个小组的右边 * 界下标，然后将新的两个小组继续划分，调用 * 自身进行递归 */ int m = (left+right) / 2; mergeUpSort(nums, left, m); mergeUpSort(nums, m+1, right); /** * 当分组完成之后就合并子数组 */ mergeUp(nums, left, m+1, right); }值得注意的一点是，这种递归方式实际运行出来的过程跟开头描述的过程并不完全相符，在开头是将所有的数都先分成了只有一个数的小组，但在上述递归中，是只要有相邻两个小组不可再分之后就会提前返回开始第一次合并(因为上述递归它永远是先递归小组的左半部分，右半部分是不动的，只有左边分完并且合并完了，才会返回并开始递归右半部分)，并且，由于上述的 m 表示的是下标，实际分组也不是均分的(因为数组下标是从 0 开始的，而 一开始 m = 10 / 2 = 5，表示左半部分为 A[0] ~ A[5] 这 6 个数，右半部分只有 4 个数，但其实影响不大，是为了方便说明每个参数的实际意义才取成下标的)，虽然执行过程并不完全相符，但是思想却是一致的。 升序部分实现完成之后，降序只需要在合并时先放入更大的数即可
