归并排序

归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。

具体步骤，大致可分为2步：拆分与合并；

先将待排数组从中间位置一分为二，将拆分的两部分在一分为二，以此拆分直到仅有一个元素时，不可再分。拆完了，接着就是合并，我们需要将两个已经有序的子序列合并成一个有序序列，我们比较2个子序列的头部，将小的(或大的)存入一个临时的数组中，在移动头部的位置，知道两个子序列的所有元素都放入临时数组中，将合并的有序临时数组的元素在覆盖到原数组中，实现排序。

代码如下：