PHP归并排序求最小和

/**
 *
 * 归并求数组的最小和
 *
 * @param array $arr
 * @return array
 */
function minSumByMergeSort(array &$arr) {
      $len = count($arr);
      if (!$len || empty($arr)) {
            return 0;
      }

      mergeSort($arr, 0, $len-1);
}

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

      $middle = $left + (($right - $left) >> 1);

      return mergeSort($arr, $left, $middle)
          + mergeSort($arr, $middle+1, $right)
          + mergeArray($arr, $left, $middle, $right);
}

/**
 *
 * 把两个有序的数组合并成一个有序的数组，并求出最小和
 *
 * @param array $arr
 * @param $left
 * @param $middle
 * @param $right
 * @return float|int
 */
function mergeArray(array &$arr, $left, $middle, $right) {
      $helpArr = [];
      $i = 0;
      $sum = 0;

       //定义左侧和右侧有序数组的起始索引
      $leftIndex = $left;
      $rightIndex = $middle+1;
      
      //左右两侧都不越界
      while (($leftIndex <= $middle) && ($rightIndex <= $right)) {
          $sum += $arr[$leftIndex] < $arr[$rightIndex] ? ($right - $rightIndex + 1) * $arr[$leftIndex] : 0;
          $helpArr[$i++] = $arr[$leftIndex] < $arr[$rightIndex] ? $arr[$leftIndex++] : $arr[$rightIndex++];
      }

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

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

      $helpLen = count($helpArr);

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

      return $sum;
}