正文：
归并排序：它是使用了一种分治递归的思想去解决我们的无序数据列。
分治法：分而治之。
下面这张图讲解一下归并的思想：
我们可以看出来归并的排序的步骤就是：
1.先把我们的序列按照对半分拆，一直分拆到每个子序列只有一个数据。
2.对我们每个子序列进行我们的递归排序
3.把排好的子序列进行归并，得到我们最终排好序列。
在这里要解释一下治的过程。我们是用一个和原序列相同大小的数组tmp去存放每次子序列中被筛选后的数。所谓被筛选的数就是两个子序列分别从自己的开头遍历到结尾去进行比较并且按照一定的规则（比如把较小的放入tmp中）去给tmp中放数据，当一个子序列全部已经放入tmp中时。这时就把和它比较的另一个子序列直接全部放入tmp中。然后把tmp中数据在返回给我们的原序列。
我们可以从上图中来看，8和4就是2个子序列，4比8小，因此4放入tmp中，这时4的子序列已经没有数据了，也就是意味着全部已经放入了tmp中，那么我们就把8直接紧跟着放入tmp中。那么tmp返回给原序列就是以4,8的形式返回，后面同理，即可完成我们的排序。
下面是代码实现：
void Sortjust(int *arr, int first, int mid, int last, int *brr)
{
int i = first; //左有序小段的首位置
int j = mid + 1; //右有序小段的首位置
int k = first; //存放比较后数据数组的首位置
while (i<=mid && j <=last) //判断2个序列小段比较有没有越界
{
if (arr[i] < arr[j]) //将左序列和右序列进行比较，把小的数值，放到brr中
{
brr[k++] = arr[i++];
}
else
{
brr[k++] = arr[j++];
}
}
while (i <=mid) //说明右序列已经全部放入brr中，这时就把左序列紧接着全放入brr
{
brr[k++] = arr[i++];
}
while (j <=last) //说明左序列已经全部放入brr中，就把右序列紧接着放入brr
{
brr[k++] = brr[j++];
}
for (i = 0; i < k; i++) //此时的brr已经是排序好的数列，然后放回到arr中。
{
arr[i] = brr[i];
}
}
void Sort1(int *arr, int *brr,int first, int last)
{
if (first != last)
{
int mid = (first + last) / 2;
Sort1(arr,brr, first, mid); //将刚开始序列都分成了只含单个元素的序列
Sort1(arr,brr, mid + 1, last);
Sortjust(arr, first, mid, last, brr); //归并二者：去比较放入tmp 最终返回 排好序列
}
}
归并排序的时间复杂度是O(nlogn),空间复杂度是O（1）。它也是一个稳定的排序。