目录

一 基本思想二 例子三 复杂度分析四 非递归实现

一 基本思想

1.假设初始序列含有 n 个记录， 则可以看成是 n 个有序的子序列， 每个子序列的长度为1， 然后两两归并，得到[ n / 2] （[x] 表示不少于 x 的 最小整数）个长度为2 或 1 的有序子序列，；再两两归并，······，如此重复， 直至得到一个长度为 n 的有序序列为止， 这种排序方法称为2路归并排序。

二 例子

public static void Sort(int[] array, int startIndex, int endIndex) { if (startIndex < endIndex) { int middleIndex = (startIndex + endIndex)/2; Sort(array, startIndex, middleIndex); // 递归区间在(startIndex , middleIndex]的元素， 使之有序 Sort(array, middleIndex + 1, endIndex);// 递归区间在(middleIndex+1,endIndex]的元素， 使之有序 MergeArray(array, startIndex, middleIndex, endIndex); // 归并两个有序区间的元素 } } private static void MergeArray(int[] array, int startIndex, int middleIndex, int endIndex) { int[] temp = new int[endIndex - startIndex + 1]; int i = startIndex; int j = middleIndex + 1; int index = 0; while (i <= middleIndex && j <= endIndex) { //比较区间在(startIndex , middleIndex] 和 (middleIndex+1,endIndex]数列（因为数列内部是有序的）的值， 谁小取谁。 //直到 i > middleIndex 或者 j > endIndex,退出循环，此时 temp[] 是有序的 if (array[i] < array[j]) { temp[index++] = array[i++]; } else { temp[index++] = array[j++]; } } while (i <= middleIndex) // 说明区间在(startIndex , middleIndex]的元素还有值没存进temp[]， 把剩余的元素存进去 { temp[index++] = array[i++]; } while (j <= endIndex) // 说明区间在(middleIndex+1,endIndex]的元素还有值没存进temp[]， 把剩余的元素存进去 { temp[index++] = array[j++]; } for (int m = 0; m < temp.Length; m++) //更新array中区间在[startIndex, endIndex]元素的位置， 使之有序。 { array[startIndex + m] = temp[m]; } }

三 复杂度分析

一次归并操作需要将区间在[startIndex， endIndex]中元素归并在一起，此过程的时间复杂度可记为O(n)。 由完全二叉树的深度可知， 整个归并过程， 需要调用 [ log₂ n ] 次 归并操作， 因此时间复杂度可认为是 O(nlog₂ n)

四 非递归实现

public static void Sort(int[] array) { int len = 1; while (len < array.Length) { for (int i = 0; i + len < array.Length; i = i + 2 * len) { int startIndex = i; int middleIndex = startIndex + len - 1; int endIndex = middleIndex + len; if (endIndex >= array.Length) { endIndex = array.Length - 1; } MergeArray(array, startIndex, middleIndex, endIndex); } len *= 2; } }