归并排序，是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。核心思想是将两个已经排序好的序列，合并成一个排序的序列。

算法步骤
1、以递归的方式将一个数组从中间拆分成两个子数组，一直拆分下去，直到子数组中值剩下一个元素为止；
2、分别从两个子数组的开头取值进行比较，小（大）的放入一个新数组，并且继续下一轮比较，直到其中一个数组中的值被取光为止；
3、然后把还没有取完的值的子数组取出来放到新数组的最后；
4、将新的有序数组替换到原数组相应的位置上去。

动图演示

代码实现：

public function mergeSort(array $arr)
{
    $len = count($arr);
    if ($len < 2) {
        return $arr;
    }
    $middle = floor($len / 2); // 将数组一分为二
    $left = array_slice($arr, 0, $middle);
    $right = array_slice($arr, $middle);
    
    return $this->merge($this->guibing($left), $this->guibing($right)); // 将已经一分为二的数组继续一分为二，直到每个子数组中都只有一个值，然后通过比较+合并返回新数组给
}

//合并两个有序数组
private function merge(array $left, array $right)
{
    $result = [];
    
    while (count($left) > 0 && count($right) > 0) {
        if ($left[0] <= $right[0]) {
            $result[] = array_shift($left);
        } else {
            $result[] = array_shift($right);
        }
    }
    
    while (count($left)) { // 将左边子数组中还没有取完的值，取出来放到新数组中
        $result[] = array_shift($left);
    }
    
    while (count($right)) { // 将右边子数组还没有取完的值，取出来放到新数组中
        $result[] = array_shift($right);
    }
    
    return $result;
}