归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
先递归的把数组划分为两个子数组，一直递归到数组中只有一个元素，然后再调用函数把两个子数组排好序，因为该函数在递归划分数组时会被压入栈，所以这个函数真正的作用是对两个有序的子数组进行排序；
基本步骤
- 判断参数的有效性，也就是递归的出口；
- 首先什么都不管，直接把数组平分成两个子数组；
- 递归调用划分数组函数，最后划分到数组中只有一个元素，这也意味着数组是有序的了；
- 然后调用排序函数，把两个有序的数组合并成一个有序的数组；
- 排序函数的步骤，让两个数组的元素进行比较，把大的/小的元素存放到临时数组中，如果有一个数组的元素被取光了，那就直接把另一数组的元素放到临时数组中，然后把临时数组中的元素都复制到实际的数组中；
归并的时间复杂度分析,主要是考虑两个函数的时间花销：数组划分函数divide()、有序数组归并函数merge()；
merge()函数的时间复杂度为O(n)，因为代码中有4个长度为n的循环（非嵌套），所以时间复杂度则为O(n)；
简单的分析下元素长度为n的归并排序所消耗的时间 T[n]：调用divide()函数划分两部分，那每一小部分排序好所花时间则为 T[n/2]，而最后把这两部分有序的数组合并成一个有序的数组merge()函数所花的时间为 O(n)；
公式：T[n] = 2T[n/2] + O(n)；
推导过程：
T(n) = 2T(n/2)+O(n)
= 2(2T(n/4)+O(n/2))+O(n)
= 2(2(2T(n/8)+O(n/4))+O(n/2))+O(n) = 8T(n/8)+[4O(n/4)+2O(n/2)+O(n)]
n = 2^k
[ ] = n*lgn
2^kT(n/2^k) = cn
T(n) = n*lgn + cn = n*lgn
结果：T[n] = O(nlogn)