マージソート

「ドレッシング屋さんと作った、おいしい揚もち」を食べた。やっぱり、もちはもち屋だな、と思った。

JavaのArraysクラスのmergeSort()をPHPにそのままコピーしてみました。

<?php

define('INSERTIONSORT_THRESHOLD', 7);

function mergeSrot(&$a, $cmp) {
	$temp = $a;
	_mergeSort($temp, $a, 0, count($a), 0, $cmp);
}

function _mergeSort(&$src, &$dest, $low, $high, $off, $cmp) {
	$length = $high - $low;

	// Insertion sort on smallest arrays
	if ($length < INSERTIONSORT_THRESHOLD) {
		for ($i = $low; $i < $high; $i++) {
			for ($j = $i; $j > $low && $cmp($dest[$j-1], $dest[$j]) > 0; $j--) {
				swap($dest, $j, $j-1);
			}
		}
		return;
	}

	// Recursively sort halves of dest into src
	$destLow = $low;
	$destHigh = $high;
	$low += $off;
	$high += $off;
	$mid = ($low + $high) >> 1;
	_mergeSort($dest, $src, $low, $mid, -$off, $cmp);
	_mergeSort($dest, $src, $mid, $high, -$off, $cmp);

	// If list is already sorted, just copy from src to dest.This is an
	// optimization that results in faster sorts for nearly ordered lists.
	if ($cmp($src[$mid-1], $src[$mid]) <= 0) {
	//	System.arraycopy(src, low, dest, destLow, length);
		for ($i = 0; $i < $length; $i++) {
			$dest[$i+$destLow] = $src[$i+$low];
		}
		return;
	}

	// Merge sorted halves (now in src) into dest
	for($i = $destLow, $p = $low, $q = $mid; $i < $destHigh; $i++) {
		if ($q >= $high || ($p < $mid && $cmp($src[$p], $src[$q]) <= 0)) {
			$dest[$i] = $src[$p++];
		} else {
			$dest[$i] = $src[$q++];
		}
	}
}

/**
 * Swaps x[a] with x[b].
 */
function swap(&$x, $a, $b) {
	$t = $x[$a];
	$x[$a] = $x[$b];
	$x[$b] = $t;
}
?>

で、PHPの標準関数と勝負してみました。

<?php

define('INSERTIONSORT_THRESHOLD', 7);


$src = makeArray(1000000, 0, 10000000);

// uksort
$usort = $src;

$start = microtime_float();
usort($usort, "compare");
$stop = microtime_float();
$time = $stop - $start;

echo $time . " sec\n";

if ($src == $usort) echo "error 1\n";
if (!arrayCheck($usort)) echo "error 2\n";


// mergeSort
$msort = $src;

$start = microtime_float();
mergeSrot($msort, "compare");
$stop = microtime_float();
$time = $stop - $start;

echo $time . " sec\n";

if ($src == $msort) echo "error 3\n";

if (!arrayCheck($msort)) echo "error 4\n";


//////// utility ////////////

function arrayCheck(&$a) {
	$size = count($a) - 1;
	for ($i = 0; $i < $size; $i++) {
		if ($a[$i+1] - $a[$i] < 0) {
			return false;
		}
	}
	return true;
}

function makeArray($size, $min, $max) {
	$retval = array();
	for ($i = 0; $i < $size; $i++) {
		$retval[] = mt_rand($min, $max);
	}
	return $retval;
}

function microtime_float()
{
    list($usec, $sec) = explode(" ", microtime());
    return ((float)$usec + (float)$sec);
}


function compare($a, $b) {
	return $a - $b;
}

?>

結果。

41.7835450172 sec
109.330156088 sec

負けた。まあ、当たり前か。でも健闘してるんじゃないかと。使える場面もあるんじゃないかなぁ、安定ソートだし。
phpのソートは不安定ソートっぽいです。

class SortTest {
	var $a;
	var $b;
	
	function SortTest($a, $b) {
		$this->a = $a;
		$this->b = $b;
	}
}

function compare($a, $b) {
	return $a->a - $b->a;
}

$array = array();
$array[] = new SortTest(1, 1);
$array[] = new SortTest(1, 2);
$array[] = new SortTest(2, 3);
$array[] = new SortTest(2, 4);
$array[] = new SortTest(1, 5);
$array[] = new SortTest(1, 6);
$array[] = new SortTest(3, 7);
$array[] = new SortTest(3, 8);
$array[] = new SortTest(2, 9);
$array[] = new SortTest(2, 10);
$array[] = new SortTest(3, 11);


usort($array, "compare");

print_r($array);

以上