归并排序是效率还是比较高的算法。其中的分治法是常用的一种解决问题的方法，现在流行的云计算其实就是一种分治法的应用。

所谓的分治法，字面解释就是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个思想在实际工作中的作用非常大，特别是处理大数据和做复杂运算的时候。

归并排序的基础是归并操作merge，即将两个有序数组合并为一个有序数组。

归并排序的算法思路为：
第一次扫描数组，将数组中相邻的两个元素merge为有序数组
第二次扫描，将相邻的有序数组再合并为更大的一个有序数组
再进行n次扫描，不断合并数组，直到排序完成

其中的归并操作merge的思路是：
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针达到序列尾
将另一序列剩下的所有元素直接复制到合并序列尾

好了我们按照上面的思路来用PHP实现归并排序算法：

<?php

// 首先定义归并操作merge函数

function merge($arr1, $arr2){

    $arr3 = array();

    while(!empty($arr1) && !empty($arr2)){

        // 比较第一个元素，取较小的值

        $arr3[] = $arr1[0] <= $arr2[0] ? array_shift($arr1) : array_shift($arr2);

    }

    // 剩下的$arr1和$arr2中都是较大的值，且他们是有序的，故可以直接合并到$arr3后面

    $arr3 = array_merge($arr3, $arr1, $arr2);

    return $arr3;

}

   

// 归并排序算法

function merge_sort($arr){

    if(count($arr) <= 1) return $arr;

    // 将大数组拆分为连个数组

    $mid = intval(count($arr)/2);

    $arr1 = array_slice($arr, 0, $mid);

    $arr2 = array_slice($arr, $mid);

    // 利用递归思想，不断拆分数组，再逐步merge回来

    return merge(merge_sort($arr1), merge_sort($arr2));

}

   

$arr = array(5,2,4,7,1,3,2,6);

   

var_dump(merge_sort($arr));