归并排序，是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个有序的子序列，再把有序的子序列合并为整体有序序列。该算法是采用分治法。
原理：
1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 2.设定两个指针，最初位置分别为两个已经排序序列的起始位置 3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 4.重复步骤3直到某一指针超出序列尾，将另一序列剩下的所有元素直接复制到合并序列尾
图示：
上图中首先把一个未排序的序列从中间分割成2部分，再把2部分分成4部分，依次分割下去，直到分割成一个一个的数据，再把这些数据两两归并到一起，使之有序，不停的归并，最后成为一个排好序的序列。
代码语言：javascript复制 static int[] MergeSort(int[] arr,int lowIndex,int highIndex)
{
//子表的长度大于1，则进入下面的递归处理
if (lowIndex <highIndex)
{
//分割位点midIndex
int midIndex = (lowIndex highIndex) / 2;
//递归划分二部分 (arr[lowIndex].....arr[midIndex]) 、 (arr[midIndex 1].....arr[high])
MergeSort(arr, lowIndex, midIndex);
MergeSort(arr, midIndex 1, highIndex);
//归并
Merge(arr, lowIndex, midIndex, highIndex);
}
return arr;
}
//归并排序的核心部分：将两个有序的左右子表（以midIndex区分），合并成一个有序的表
private static int[] Merge(int[]arr,int lowIndex,int midIndex,int highIndex)
{
//左侧A子表 lowIndex....midIndex 右侧B子表 midIndex 1....highIndex
int[] tempArr = new int[arr.Length];
int tempIndex = 0;
int indexA = lowIndex, indexB = midIndex 1;
//左右表同时遍历比较 ，如果其中有一个子表遍历完，则跳出循环
while (indexA<=midIndex && indexB <=highIndex)
{
tempArr[tempIndex ] = (arr[indexA] <= arr[indexB] ? arr[indexA ] : arr[indexB ]);
}
//左表遍历完，右表还有数据，将右表剩余数，放入tempArr中
while(indexB<=highIndex)
{
tempArr[tempIndex ] = arr[indexB ];
}
//右表遍历完，左表还有数据，将左表剩余数，放入tempArr中
while (indexA <= midIndex)
{
tempArr[tempIndex ] = arr[indexA ];
}
//将暂存数组中有序的数列写入目标数组的制定位置，使进行归并的数组段有序
tempIndex = 0;
for (int i = lowIndex; i <=highIndex ; i )
{
arr[i] = tempArr[tempIndex ];
}
return arr;
}运行结果
代码语言：javascript复制 Console.WriteLine($"数据算法");
var arr1 = GetArrayData(20, 1,22);
Console.WriteLine($"生成未排序数据arr1：{ShowArray(arr1)}");
var arr7 = MergeSort(arr1,0,arr1.Length-1);
Console.WriteLine($"归并排序arr7：{ShowArray(arr7)}");
