介绍
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法。
占内存；
步骤
1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4. 重复步骤3直到某一指针超出序列尾；
5. 将另一序列剩下的所有元素直接复制到合并序列尾
代码
private static void MergeConsole(string location, int[] arr) { Console.Write($"{location}: "); foreach (var i in arr) { Console.Write("{0} ", i); } Console.WriteLine(); } /// <summary> /// 归并数组 /// </summary> /// <param name="arr">要归并的数组</param> /// <param name="left">归并左序列首元素下标</param> /// <param name="mid">拆分元素的下标</param> /// <param name="right">归并右序列最后元素下标</param> private static void MergeArray(int[] arr, int left, int mid, int right) { int[] temp = new int[right - left + 1]; int m = left, n = mid + 1, k = 0; while (n <= right && m <= mid) { if (arr[m] > arr[n]) { temp[k++] = arr[n++]; } else { temp[k++] = arr[m++]; } } while (n < right + 1) { temp[k++] = arr[n++]; } while (m < mid + 1) { temp[k++] = arr[m++]; } for (k = 0, m = left; m < right + 1; k++, m++) { arr[m] = temp[k]; } } /// <summary> /// 归并排序 /// </summary> /// <param name="arr">要归并的数组</param> /// <param name="left">归并左序列首元素下标</param> /// <param name="right">归并右序列最后元素下标</param> public static void MergeSort(int[] arr, int left, int right) { if (left < right) { int mid = (left + right) / 2; MergeSort(arr, left, mid); MergeConsole("_left: ", arr); MergeSort(arr, mid + 1, right); MergeConsole("right: ", arr); MergeArray(arr, left, mid, right); MergeConsole("merge: ", arr); Console.WriteLine(); } } static void Main(string[] args) { int[] array = { 149, 100, 112, 38, 80, 35, 615, 297, 592, 976, 143, 217 }; MergeSort(array, 0, array.Length - 1); Console.ReadLine(); }
性能分析
1. 时间复杂度：O（n log n），最好、最坏、平均时间复杂度都是一样的，因为不关心要排序的数组初始状态；
2. 空间复杂度：O（n），在任意时刻只有一个函数执行，只有一个临时的内存空间在使用；
3. 稳定性： 稳定；相同的值可以选择是放在左边还是右边的。