归并排序（C#实现）

归并（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)。