<?php
function __merge($list, $l, $mid, $r)
{
    $tmp = array();
    for ($i = $l; $i <= $r; $i++) {
        $tmp[$i - $l] = $list[$i];
    }
    $i = $l;
    $j = $mid + 1;
    for ($k = $l; $k <= $r; $k++) {
        if ($i > $mid) {
            $list[$k] = $tmp[$j - $l];
            $j++;
        } else if ($j > $r) {
            $list[$k] = $tmp[$i - $l];
            $i++;
        } else if ($tmp[$i - $l] < $tmp[$j - $l]) {
            $list[$k] = $tmp[$i - $l];
            $i++;
        } else {
            $list[$k] = $tmp[$j - $l];
            $j++;
        }
    }
    unset($tmp);
    return $list;
}

function __mergesort($list, $l, $r)
{
    if ($l >= $r) return '';
    $mid = floor(($l + $r) / 2);
    $rs = __mergesort($list, $l, $mid);
    if(!empty($rs)){
        $list = $rs;
    }
    unset($rs);
    $rs = __mergesort($list, $mid + 1, $r);
    if(!empty($rs)){
        $list = $rs;
    }
    unset($rs);
    $list = __merge($list, $l, $mid, $r);
    return $list;
}

function mergesort($list, $n)
{
    return __mergesort($list, 0, $n - 1);
}

function getrandlist($n)
{
    $list = array();
    for ($i = 0; $i < $n; $i++) {
        $list[$i] = rand();
    }
    return $list;
}

$n = 50000;
$a = getrandlist($n);
//var_dump($a);

echo "<br/>";
echo date('Y-m-d H:i:s.u');
echo "<br/>";
$list = mergesort($a, $n);
unset($a);
unset($list);
echo date('Y-m-d H:i:s.u');
echo "<br/>";

PHP在我电脑上运行5000数据量已经3s了,和c++50000数据量下2s的差距真大…
不知道我这样写是否有错呢?