1. 概述

  • 思路：对原序进行递归二分，至剩下两个元素进行排序，回溯过程是对前面二分并排序完成的序列进行再次排序。

  • 稳定性：稳定

    2. 实现代码

    ```php <?php class MergeSort { private array $ori = []; public array $new = []; public function __construct(array $arr) {

    1.   $this->ori = $arr;
    2.   $r = $this->sort($this->ori, 0, count($arr) - 1);
    3.   $this->new = $r;

    }

    // 递归 分割然后排序 private function sort(array $arr, int $l, int $r) {

    1.   if ($l == $r) return $arr;
    2.   // 二分分割
    3.   $mid = floor(($r - $l)/2) + $l;
    4.   // 左排序
    5.   $arr = $this->sort($arr, $l, $mid);
    6.   // 右排序
    7.   $arr = $this->sort($arr, $mid + 1, $r);
    9.   $arr = $this->merge($arr, $l, $mid + 1, $r);
    10.   return $arr;

    }

    // 将数组分割，按照 $l 和 $r 分割排序 private function merge(array $arr, int $l, int $r, int $rBound) {

    1.   $mid = $r - 1;
    3.   $tmp = [];
    5.     // 对两个有序数组排序
    6.   $i = $l;
    7.   $j = $r;
    8.   $k = 0;
    9.   while ($i <= $mid && $j <= $rBound) {
    10.       $tmp[$k++] = ($arr[$i] <= $arr[$j]) ? $arr[$i++] : $arr[$j++];
    11.   }
    13.   while ($i <= $mid) $tmp[$k++] = $arr[$i++];
    14.   while ($j <= $rBound) $tmp[$k++] = $arr[$j++];
    16.   for ($m = 0; $m < count($tmp); $m++) {
    17.       $arr[$l + $m] = $tmp[$m];
    18.   }
    19.   return $arr;

    } }

$arr = [4, 1, 7, 8, 3, 6, 9]; $cls = new MergeSort($arr);

echo implode(‘,’, $cls->new); ```