一、定义
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
二、排序演示
归并操作
归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。
如 设有数列{6，202，100，301，38，8，1}
初始状态：6,202,100,301,38,8,1
第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；
第三次归并后：{1,6,8,38,100,202,301},比较次数：4；
总的比较次数为：3+4+4=11；
逆序数为14；
算法描述
归并操作的工作原理如下：
第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
三、性能分析
归并排序先递归的把数组划分为两个子数组，一直递归到数组中只有一个元素，然后再调用函数把两个子数组排好序，因为该函数在递归划分数组时会被压入栈，所以这个函数真正的作用是对两个有序的子数组进行排序。排序函数的步骤，让两个数组的元素进行比较，把大的/小的元素存放到临时数组中，如果有一个数组的元素被取光了，那就直接把另一数组的元素放到临时数组中，然后把临时数组中的元素都复制到实际的数组中。所以 归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间n + logn，所以空间复杂度为:O(n)。
时间复杂度
归并排序的时间主要花在了划分序列和合并序列上，由于是采用递归的方式进行合并，所以与快速排序类似，树的每层元元素的个数最多是n，也就代表着每层最多进行n次比较，而递归树最多只有log2n层，而且不管元素在什么情况下都要做这些步骤，所以该算法的最优时间复杂度和最差时间复杂度及平均时间复杂度都是一样，都是O( nlogn )。
稳定性
归并排序的原理是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换)，然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也不会交换，所以不会破坏稳定性。而在短的有序序列合并的过程中，稳定性也没有受到破坏，合并过程中可以保证如果两个当前元素相等时，把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序是稳定的排序算法。
四、代码实现
function mergeSort(&$arr){
$len = count($arr);
msort($arr,0,$len-1);
}
function msort(&$arr,$low,$high){
if($low<$high){
$mid = floor(($low+$high)/2);
msort($arr, $low, $mid);
msort($arr,$mid+1,$high);
mergeArray($arr,$low,$mid,$high);
}
}
function mergeArray(&$arr,$low,$mid,$high){
$i = $low;
$j = $mid+1;
while($i<=$mid && $j<=$high){
if($arr[$i]<$arr[$j]){
$tmp[] = $arr[$i++];
}else{
$tmp[] = $arr[$j++];
}
}
while($i<=$mid){
$tmp[] = $arr[$i++];
}
while($j<=$high){
$tmp[] = $arr[$j++];
}
$len = count($tmp);
for($k=0;$k<$len;$k++){
$arr[$low+$k] = $tmp[$k];
}
}
$arr = array(1,2,3,7,9,0,4,6,5,1);
mergeSort($arr);
print_r($arr);