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