归并排序算法（Merge Sort）是一种采用分治法（Divide-And-Conquer）的排序算法。分治策略将原问题划分为n个规模较小而结构与原问题相似的子问题，递归地解决这些子问题，然后在合并其结果，就得到原问题的解。分治模式在每一层递归上都包含三个步骤：分解、解决、合并。即归并=递归＋合并。
数组分左右，左右元素相比较，满足条件放入新数组，一侧用完放对面。 递归不停分，分完再排序，排序结束往上走，边走边合并，走到头顶出结果。
递归平分数组就是不停进行分割，当长度小于2停止，然后开始比较，一层一层向上比。 而基本排序规则，左右元素进行比较，依次放入新数组中。当—侧没有的时候，另一侧直接放入新数组。
算法步骤：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
- 重复步骤 3 直到某一指针达到序列尾；
- 将另一序列剩下的所有元素直接复制到合并序列尾。
代码如下：
public static List<int> sort(List<int> lst) { if (lst.Count <= 1) return lst; int mid = lst.Count / 2; List<int> left = new List<int>(); // 定义左侧List List<int> right = new List<int>(); // 定义右侧List // 以下两个循环把 list 分为左右两个 List for (int i = 0; i < mid; i++) left.Add(lst[i]); for (int j = mid; j < lst.Count; j++) right.Add(lst[j]); left = sort(left); right = sort(right); return merge(left, right); } /// <summary> /// 合并两个已经排好序的List /// </summary> /// <param name="left">左側List</param> /// <param name="right">右側List</param> /// <returns></returns> static List<int> merge(List<int> left, List<int> right) { List<int> temp = new List<int>(); while (left.Count > 0 && right.Count > 0) { if (left[0] <= right[0]) { temp.Add(left[0]); left.RemoveAt(0); } else { temp.Add(right[0]); right.RemoveAt(0); } } if (left.Count > 0) { for (int i = 0; i < left.Count; i++) temp.Add(left[i]); } if (right.Count > 0) { for (int i = 0; i < right.Count; i++) temp.Add(right[i]); } return temp; }
