今天我们的目标是：归并排序。要理解这种排序，首先我们先了解一下归并：
归并：
现在我们要求将两个从小到大排列的有序数组归并为一个从小到大排序的有序数组。想想怎么办？常规做法就是：
1、 创建一个新数组，长度是两个数组的长度之和。
2、 运用三个指针，分别指向三个数组的头部，然后比较需要归并的数组两个指针指向的数字，得到较小者，将较小者放在新数组指针指向的位置，然后向后移动较小者数组指针，和新数组指针。
3、 重复步骤2，直到一个数组比较完毕。将未排完数组，后续的数字排到新数组的尾部。归并结束。
代码：
public static int[] Merge(int[] arr1, int[] arr2)
{
int length1 = arr1.Length;
int length2 = arr2.Length;
int[] arr = new int[length1 + length2];
int index = 0;
int i = 0;
int j = 0;
//从前往后比较两个数组的值，谁小，谁放在新数组前面
//直到一个数组比较完毕
while (i < length1 && j < length2)
{
if (arr1[i] <= arr2[j])
{
arr[index] = arr1[i];
i++;
index++;
}
else
{
arr[index] = arr2[j];
j++;
index++;
}
}
//将还没有比较的数依次放在新数组后面
while (i < length1)
{
arr[index] = arr1[i];
i++;
index++;
}
while (j < length2)
{
arr[index] = arr2[j];
j++;
index++;
}
return arr;
}
时间复杂度： 可以看到归并运行的次数为( length1+length2 )次，因此它的时间复杂度为：O（n）。
空间复杂度： O( n ) 。
归并排序：
归并排序正是利用了上述归并的思路为核心的排序方法。假设这里有一个长度为1的数组，那么无论如何他就是一个有序数组。归并排序就是不断分解数组，直到数组长度为1，然后不断归并，最后形成一个有序的数组。这种思路就是归并排序的递归实现的思路。
演示动画如下：
merge5.gif
实现方式有两种：递归和非递归。
递归方式就是不断拆分数组，直到数组长度为1，然后不断归并。
代码如下：
public static void MergeSort(int[] arr)
{
int length = arr.Length;
if (length<2)
{
return;
}
MegerSort(arr, 0, length-1);
}
public static void MergeSort(int[] arr,int left,int right)
{
//数组一分为2，不断拆分，直到数组长度为1，直接返回
if (left>= right)
{
return;
}
int mid = left+(right - left) / 2;
MergeSort(arr, left, mid);
MergeSort(arr, mid+1, right);
//按mid将数组分组，然后将两组数据归并为1组
int[] arr2 = new int[right - left+1];
int index = 0;
int i = left;
int j = mid + 1;
while (i <= mid&& j <= right)
{
if (arr[i] <= arr[j])
{
arr2[index] = arr[i];
i++;
index++;
}
else
{
arr2[index] = arr[j];
j++;
index++;
}
}
while (i <= mid)
{
arr2[index] = arr[i];
i++;
index++;
}
while (j <= right)
{
arr2[index] = arr[j];
j++;
index++;
}
for (int n = 0; n < index; n++)
{
arr[left + n] = arr2[n];
}
}
非递归方式就是利用循环，从按长度为1分组，然后归并，不断翻倍数组长度，进行归并。
代码如下：
public static void MergeSort2(int[] arr)
{
int length = arr.Length;
if (length<2)
{
return;
}
//按gap对数组进行分组，并在组内进行归并
int gap = 1;
while (gap<=length)
{
int i = 0;
int left = i * (gap * 2);
while (left< length)
{
int right = (i + 1) * (gap * 2) - 1;
//数组数组越界的情况
if (right >= length)
{
right = length - 1;
}
MergeSort2(arr, left, right);
i++;
left = i * (gap * 2);
}
gap *= 2;
}
}
//将数组分组为left-mid,mid+1-right两组进行归并
public static void MergeSort2(int[] arr,int left,int right)
{
if (right<= left)
{
return;
}
int mid = left + (right - left) / 2;
int[] arr2 = new int[right - left + 1];
int index = 0;
int i = left;
int j = mid + 1;
while (i <= mid && j <= right)
{
if (arr[i] <= arr[j])
{
arr2[index] = arr[i];
i++;
index++;
}
else
{
arr2[index] = arr[j];
j++;
index++;
}
}
while (i <= mid)
{
arr2[index] = arr[i];
i++;
index++;
}
while (j <= right)
{
arr2[index] = arr[j];
j++;
index++;
}
for (int n = 0; n < index; n++)
{
arr[left + n] = arr2[n];
}
}
时间复杂度：归并一次的时间复杂度为O（n），无论是递归，还是循环，都要执行log2n次归并。因此复杂度为：O（nlog2n）
空间复杂度：O(n)。
稳定性：稳定排序。
