PHP归并排序

/**
 *
 * 归并排序
 *
 * @param array $arr
 * @return array
 */
function mergeSort(array &$arr) {
    $len = count($arr);
    if (!$len || empty($arr)) {
        return [];
    }  
    
    process($arr, 0, $len-1);
}

/**
 *
 * 把数组arr[L...R]上调整有序
 *
 * @param array $arr
 * @param $left
 * @param $right
 * @return array
 */
function process(array &$arr, $left, $right) {
      if (intval($left) === intval($right)) {
          return $arr;
      }

      $middle = (int)($left + ($right-$left) / 2);

      process($arr, $left, $middle);
      process($arr, $middle+1, $right);
      mergeArray($arr, $left, $middle, $right);

}

/**
 *
 * 将两个有序的数组合并为有序的数组
 *
 * @param array $arr
 * @param $left
 * @param $middle
 * @param $right
 */
function mergeArr(array &$arr, $left, $middle, $right) {
      $i = 0;
      $helpArr = [];
      
      $leftIndex = $left;
      $rightIndex = $middle +1;

      //若左右两个数组都不越界
      while(($leftIndex <= $middle) && ($rightIndex <= $right)) {
            $helpArr[$i++] = $arr[$leftIndex] <= $arr[$rightIndex] ? $arr[$leftIndex++] : $arr[$rightIndex++];
      }

      //左右两个数组，一定有一个越界，另一个不越界
      while($leftIndex <= $middle) {
            $helpArr[$i++] = $arr[$leftIndex++];
      }

      while($rightIndex <= $right) {
            $helpArr[$i++] =  $arr[$rightIndex++];
      }

      $len = count($helpArr);

      for ($i = 0; $i < $len; $i++) {
            $arr[$left + $i] = $help[$i];
      }

}