一、基本原理：
//归并 = 递归 + 合并
//数组分左右
//左右元素相比较
//满足条件放入新数组
//一侧用完放对面
//递归不停分 分完在排序
//排序结束往上走 边走边合并
//走到头顶出结果
//归并排序分为两部分
//1.基本排序规则
//2.递归平分数组
//递归平分数组：
//不停地分割，长度小于2停止
//开始比较
//一层一层向上比较
//基本排序规则：
//左右元素进行比较
//依次放入新数组
//一侧没有了另一侧直接放入新数组
二、图像说明原理
这是原始数组，由于是不断的平分数组，所以除以二取整就是4第一次分割为，8 7 1 5 和 4 2 6 3 9 两个部分
继续向下分割直到分为每个新数组只有一个元素为止
切割完毕后我们就可以开始排序了，这里我们选择升序排列
这里以8 7为例介绍 left为一个数组 right为一个数组，用来记录取的元素。在这里，由于我们是进行升序排列，所以left数组第0个元素和right数组第0个元素相比较，由于right数组第0个元素小于left第0个元素，所以先把7放到新数组，然后right加一，此时由于该元素7已经放入新数组了。所以right数组元素为空，故直接将left数组元素全部放入新数组，然后left加一。这里比较完毕后，同时本轮的其他成员也会进行比较。
接下来我们比较6 3 9 由于3 9 在下一层次，所以得先将3 9 自己比较完毕后才能和6比较，这连个元素的比较方法和前面一样不赘述。将获得的新数组和6进行一一比较排序
这里，将3 9 获得的新数组与6进行比较排序，右边第0个元素3小于6放入到新数组，然后right+1，然后继续比较左边第0个元素和右边第1个元素，发现6<9所以将6放入到新数组，left+1,此时左边数组没有元素了，直接将右侧元素全部放入即可然后right再+1
如此反复即可得到一个最终有序的数组，所以我们需要用到递归的思想，反复调用代码。
三、代码实现
①先得有一个数组
int[] arr = new int[] { 8, 7, 1, 5, 4, 2, 6, 3, 9 };②由于之前不断的需要将数组平分和排序，这里需要不断的递归自己，所以肯定不能想到在主函数里面进行代码的编写，肯定需要另外单独写函数，然后调用。需要排序函数和平分函数。先来写排序函数。
怎么写呢 由于需要将元素重新装到一个新数组，所以得申明一个新数组 和左右索引，而这个函数的目的是为了排序左右数组最后返回一个新数组，所以返回值是int[]，传参是两个数组，新数组的长度肯定不会超过左右两个数组的长度之和，所以这样申明
public static int[] Sort(int[] left, int[] right)
{
//先准备一个新数组
int[] array = new int[left.Length + right.Length];
int leftIndex = 0;
int rightIndex = 0;
return array;
}这是整体框架，然后我们想着写排序逻辑，由于需要获取到每个元素，所以我们利用for循环获取每个元素。
for (int i = 0; i < array.Length; i++)
{
}现在可以在里面写排序逻辑了。
有什么条件可以写呢
1.左边放完了直接放右边元素
//意味着左侧数组已经全部放入新数组 该放对面了
if (leftIndex >= left.Length)
{
array[i] = right[rightIndex];
rightIndex++;
}2.右边放完了直接放左边元素
//意味着右侧数组已经全部放入新数组 该放对面了
else if (rightIndex >= right.Length)
{
array[i] = left[leftIndex];
leftIndex++;
}3.右边元素大于左边元素将左边元素放入新数组
else if (left[leftIndex] < right[rightIndex])
{
array[i] = left[leftIndex];
//已经放入了一个左侧元素进入新数组
//所以标识指向下一个
leftIndex++;
}4左边元素大于右边元素将右边元素放入新数组
else
{
array[i] = right[rightIndex];
//已经放入了一个右侧元素进入新数组
//所以标识指向下一个
rightIndex++;
}最后将数组返回出去即可
排序函数完整代码：
public static int[] Sort(int[] left, int[] right)
{
//先准备一个新数组
int[] array = new int[left.Length + right.Length];
int leftIndex = 0;
int rightIndex = 0;
//最终目的是填满这个新数组
//不会出现两侧都放完了 还在进循环
//因为这个新数组的长度 是根据左右两个数组的长度计算出来的
for (int i = 0; i < array.Length; i++)
{
//意味着左侧数组已经全部放入新数组 该放对面了
if (leftIndex >= left.Length)
{
array[i] = right[rightIndex];
rightIndex++;
}
//意味着右侧数组已经全部放入新数组 该放对面了
else if (rightIndex >= right.Length)
{
array[i] = left[leftIndex];
leftIndex++;
}
else if (left[leftIndex] < right[rightIndex])
{
array[i] = left[leftIndex];
//已经放入了一个左侧元素进入新数组
//所以标识指向下一个
leftIndex++;
}
else
{
array[i] = right[rightIndex];
//已经放入了一个右侧元素进入新数组
//所以标识指向下一个
rightIndex++;
}
}
//得到了新数组 直接返回新数组
return array;
}③接下来写平分函数 由于最后传出的是最终结果 要把最初的数组传入 然后平分 所以这样申明
public static int[] Merge(int[] array)
{
}
1. 初始化
//1.数组分两段 得到一个中间索引
int mid = array.Length / 2;
//2.初始化左右数组
//左数组
int[] left = new int[mid];
//右数组
int[] right = new int[array.Length - mid];
//左右初始化内容
for (int i = 0; i < array.Length; i++)
{
if (i < mid)
left[i] = array[i];
else
right[i - mid] = array[i];
}2.这里是不是就获取到了两个数组，只要将他们不断的平分平分再平分就可以得到最小的数组然后进行排序，关键代码
//3.递归再分再排序
return Sort(Merge(left), Merge(right));3.由于是在递归自己，需要有结束条件，结束条件写在函数最开始，不过咱们需要怎样的结束条件呢，当然是数组长度小于2时
//递归结束条件
if (array.Length < 2)
{
return array;
}该函数完整代码：
public static int[] Merge(int[] array)
{
//递归结束条件
if (array.Length < 2)
{
return array;
}
//1.数组分两段 得到一个中间索引
int mid = array.Length / 2;
//2.初始化左右数组
//左数组
int[] left = new int[mid];
//右数组
int[] right = new int[array.Length - mid];
//左右初始化内容
for (int i = 0; i < array.Length; i++)
{
if (i < mid)
left[i] = array[i];
else
right[i - mid] = array[i];
}
//3.递归再分再排序
return Sort(Merge(left), Merge(right));
}四、运行结果
五、总结
//基本原理 归并=递归+合并
//数组分左右 左右元素相比较
//一侧用完放对面
//不停放入新数组
//递归不停分
//分完在排序
//排序结束往上走
//边走边合并
//走到头顶出结果
//套路写法
//两个函数
//一个基本排序规则
//一个递归平分数组
//注意事项
//排序规则函数 在平分数组函数里调用
//内部return调用
六、完整代码
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 归并排序
{
internal class Program
{
static void Main(string[] args)
{
int[] arr = new int[] { 8, 7, 1, 5, 4, 2, 6, 3, 9 };
arr = Merge(arr);
for (int i = 0; i < arr.Length; i++)
{
Console.WriteLine(arr[i]);
}
Console.ReadKey();
}
#region 归并排序的代码实现
//第一步：
//基本排序规则
//左右元素进行比较
//满足条件放进去
//一侧没有了放对面
public static int[] Sort(int[] left, int[] right)
{
//先准备一个新数组
int[] array = new int[left.Length + right.Length];
int leftIndex = 0;
int rightIndex = 0;
//最终目的是填满这个新数组
//不会出现两侧都放完了 还在进循环
//因为这个新数组的长度 是根据左右两个数组的长度计算出来的
for (int i = 0; i < array.Length; i++)
{
//意味着左侧数组已经全部放入新数组 该放对面了
if (leftIndex >= left.Length)
{
array[i] = right[rightIndex];
rightIndex++;
}
//意味着右侧数组已经全部放入新数组 该放对面了
else if (rightIndex >= right.Length)
{
array[i] = left[leftIndex];
leftIndex++;
}
else if (left[leftIndex] < right[rightIndex])
{
array[i] = left[leftIndex];
//已经放入了一个左侧元素进入新数组
//所以标识指向下一个
leftIndex++;
}
else
{
array[i] = right[rightIndex];
//已经放入了一个右侧元素进入新数组
//所以标识指向下一个
rightIndex++;
}
}
//得到了新数组 直接返回新数组
return array;
}
//第二步：
//递归平分数组
//不停地分割，长度小于2停止
public static int[] Merge(int[] array)
{
//递归结束条件
if (array.Length < 2)
{
return array;
}
//1.数组分两段 得到一个中间索引
int mid = array.Length / 2;
//2.初始化左右数组
//左数组
int[] left = new int[mid];
//右数组
int[] right = new int[array.Length - mid];
//左右初始化内容
for (int i = 0; i < array.Length; i++)
{
if (i < mid)
left[i] = array[i];
else
right[i - mid] = array[i];
}
//3.递归再分再排序
return Sort(Merge(left), Merge(right));
}
#endregion
}