归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个有序的子序列，再把有序的子序列合并为整体有序序列。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法。
c#代码
1 public static void MergeSort(int[] inputAray, int first, int end)
2 {
3 if (first < end)
4 {
5 int midIndex = (first + end) / 2;
6 MergeSort(inputAray, first, midIndex);
7 MergeSort(inputAray, midIndex + 1, end);
8 MergeMethid(inputAray, first, midIndex, end);
9 }
10 }
11
12 private static void MergeMethid(int[] inputAray, int first, int midIndex, int end)
13 {
14 int[] temp = new int[end - first + 1];
15 int m = first;
16 int n = midIndex + 1;
17 int k = 0;
18 while (m <= midIndex && n < end)
19 {
20 if (inputAray[m] < inputAray[n])
21 {
22 temp[k] = inputAray[m];
23 k++;
24 m++;
25 }
26 else
27 {
28 temp[k] = inputAray[n];
29 k++;
30 n++;
31 }
32 }
33 while (m <= midIndex)
34 {
35 temp[k] = inputAray[m];
36 k++;
37 m++;
38 }
39 while (n < end)
40 {
41 temp[k] = inputAray[n];
42 k++;
43 n++;
44 }
45 for (k=0,m = first; m < end; k++,m++)
46 {
47 inputAray[m] = temp[k];
48 }
49
50 }
归并排序是稳定的排序。速度仅次于快速排序。时间复杂度O(nlgn)。