ソートアルゴリズムについて調べてみた

結構な量のソートアルゴリズムをやってみた。
ここら辺を参考に。
　
ソート - Wikipedia
http://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC%E3%83%88
　
ヒープソートは、かなり短くした。
可読性は酷いもんだ。
　
気が向いたら他のアルゴリズムも追記するかも知れない。
　

実行結果

$ php ArraySort.php
array count: 100
sort time: 0.0000970364
----------------------------------------
o bubbleSort                0.0033838749
o cocktailSort              0.0030219555
o oddEvenSort               0.0033051968
o combSort                  0.0007081032
o gnomeSort                 0.0035710335
o quickSort                 0.0007450581
o selectionSort             0.0014488697
o heapSort                  0.0028982162
o smoothSort                0.0220639706
- cartesianTreeSort         0.0000030994
o tournamentSort            0.0256109238
o cycleSort                 0.0067420006
o insertionSort             0.0011010170
o binaryInsertionSort       0.0010468960
o shellSort                 0.0004940033
o treeSort                  0.0109040737
o librarySort               0.0018830299
o patienceSort              0.0018470287
o mergeSort                 0.0016689301
- polyphaseMergeSort        0.0000030994
o strandSort                0.0016798973
o timSort                   0.0216958523
o radixSort                 0.0009479523
o bucketSort                0.0001828671
o countingSort              0.0001790524
o pigeonholeSort            0.0002150536
- burstSort                 0.0000028610
- beadSort                  0.0000030994
- topologicalSort           0.0000019073
o bitonicSort               0.0220050812
o batcherOddEvenMergeSort   0.0182960033
o pancakeSort               0.0044078827
x bogoSort                  0.0032398701
o stoogeSort                0.4778499603

ソース

ArraySort.php

<?php

ArraySort::test();


class ArraySort
{
	/* test*/

	public static function test($size=100)
	{
		$arr = array();
		for ($i=0; $i<$size; $i++) {
			$arr[] = mt_rand(0, 100);
		}
		$valid = $arr;

		$b = microtime(1);
		sort($valid, SORT_NUMERIC);
		printf("array count: %d\n", count($arr));
		printf("sort time: %.10f\n", microtime(1) - $b);
		echo "----------------------------------------\n";

		$algos = get_class_methods("ArraySort");
		foreach ($algos as $algo) {
			if (substr($algo, -4)=='Sort') {
				$result = null;
				$bench = microtime(true);
				try {
					$result = ArraySort::$algo($arr);
				} catch (Exception $e) {
				}
				$bench = microtime(true) - $bench;
				$status = $result ? (self::isSorted($result) ? 'o' : 'x') : '-';
				printf("%s %-25s %.10f\n", $status, $algo, $bench);
/*
				if ($status=='x') {
					print_r($result);
				}
*/
			}
		}
	}


	/* 交換ソート */

	// バブルソート
	public static function bubbleSort(array $array)
	{
		$n = count($array) - 1;
		for ($i=0; $i<$n; $i++) {
			for ($j=$n; $i<$j; $j--) {
				if ($array[$j]<$array[$j-1]) {
					list($array[$j], $array[$j-1]) = array($array[$j-1], $array[$j]);
				}
			}
		}
		return $array;
	}

	// シェーカーソート
	public static function cocktailSort(array $array)
	{
		$left = 0;
		$right = count($array) - 1;
		while ($left<$right) {
			for ($i=$left; $i<$right; $i++) {
				if ($array[$i+1]<$array[$i]) {
					list($array[$i], $array[$i+1]) = array($array[$i+1], $array[$i]);
					$change = $i;
				}
			}
			$right = $change;
			for ($i=$right; $left<$i; $i--) {
				if ($array[$i]<$array[$i-1]) {
					list($array[$i], $array[$i-1]) = array($array[$i-1], $array[$i]);
					$change = $i;
				}
			}
			$left = $change;
		}
		return $array;
	}

	// 奇偶転置ソート
	public static function oddEvenSort(array $array)
	{
		$flag = true;
		$n = count($array) - 1;
		while ($flag) {
			$flag = false;
			for ($i=0; $i<$n; $i+=2) {
				if ($array[$i+1]<$array[$i]) {
					list($array[$i], $array[$i+1]) = array($array[$i+1], $array[$i]);
					$flag = true;
				}
			}
			for ($i=1; $i<$n; $i+=2) {
				if ($array[$i+1]<$array[$i]) {
					list($array[$i], $array[$i+1]) = array($array[$i+1], $array[$i]);
					$flag = true;
				}
			}
		}
		return $array;
	}

	// コムソート
	public static function combSort(array $array)
	{
		$count = count($array);
		$h = floor($count / 1.3);
		while (true) {
			$swap = false;
			for ($i=0; $i+$h<$count; $i++) {
				if ($array[$i+$h]<$array[$i]) {
					list($array[$i], $array[$i+$h]) = array($array[$i+$h], $array[$i]);
					$swap = true;
				}
			}
			if ($h==1) {
				if (!$swap) {
					break;
				}
			} else {
				$h = floor($h / 1.3);
			}
		}
		return $array;
	}

	// ノームソート
	public static function gnomeSort(array $array)
	{
		$count = count($array) -1;
		for ($i=0; $i<$count; $i++) {
			if ($array[$i+1]<$array[$i]) {
				list($array[$i], $array[$i+1]) = array($array[$i+1], $array[$i]);
				if (0<$i) {
					$i -= 2;
				}
			}
		}
		return $array;
	}

	// クイックソート
	public static function quickSort(array $array)
	{
		$count = count($array);
		if ($count<=1) {
			return $array;
		}
		$pivot = $array[0];
		$left = array();
		$right = array();
		for ($i=1; $i<$count; $i++) {
			if ($array[$i]<=$pivot) {
				$left[] = $array[$i];
			} else {
				$right[] = $array[$i];
			}
		}
		$left = self::quickSort($left);
		$right = self::quickSort($right);
		return array_merge($left, array($pivot), $right);
	}


	/* 選択ソート */

	// 選択ソート
	public static function selectionSort(array $array)
	{
		$count = count($array);
		for ($i=0; $i<$count-1; $i++) {
			$min = $i;
			for ($j=$i+1; $j<$count; $j++) {
				if ($array[$j]<$array[$min]) {
					$min = $j;
				}
			}
			list($array[$i], $array[$min]) = array($array[$min], $array[$i]);
		}
		return $array;
	}

	// ヒープソート
	public static function heapSort(array $array)
	{
		$count = count($array);
		for ($i=0; $i<$count; $i++) {
			$root = floor(($count - $i) / 2) - 1;
			for ($j=$root; 0<=$j; $j--) {
				// 左下
				if ($array[$j*2+1+$i]<$array[$j+$i]) {
					list($array[$j+$i], $array[$j*2+1+$i]) = array($array[$j*2+1+$i], $array[$j+$i]);
				}
				// 右下
				if (isset($array[$j*2+2+$i]) && $array[$j*2+2+$i]<$array[$j+$i]) {
					list($array[$j+$i], $array[$j*2+2+$i]) = array($array[$j*2+2+$i], $array[$j+$i]);
				}
			}
		}
		return $array;
	}

	// スムースソート
	public static function smoothSort(array $array)
	{
		require_once 'SmoothSort.php';
		SmoothSort::sort($array);
		return $array;
	}

	// デカルト木ソート
	public static function cartesianTreeSort(array $array)
	{
		// todo
	}

	// トーナメントソート
	public static function tournamentSort(array $array)
	{
		require_once 'TournamentSort.php';
		TournamentSort::sort($array);
		return $array;
	}

	// サイクルソート
	public static function cycleSort(array $array)
	{
		for ($cycleStart=0; $cycleStart<count($array)-1; $cycleStart++) {
			$item = $array[$cycleStart];

			$pos = $cycleStart;
			for ($i=$cycleStart+1; $i<count($array); $i++) {
				if ($array[$i]<$item) {
					$pos++;
				}
			}

			if ($pos==$cycleStart) {
				continue;
			}

			while ($item==$array[$pos]) {
				$pos++;
			}
			list($array[$pos], $item) = array($item, $array[$pos]);

			while ($pos!=$cycleStart) {
				$pos = $cycleStart;
				for ($i=$cycleStart+1; $i<count($array); $i++) {
					if ($array[$i]<$item) {
						$pos++;
					}
				}
				while ($item==$array[$pos]) {
					$pos++;
				}
				list($array[$pos], $item) = array($item, $array[$pos]);
			}
		}
		return $array;
	}


	/* 挿入ソート */

	// 挿入ソート
	public static function insertionSort(array $array)
	{
		$count = count($array);
		for ($i=1; $i<$count; $i++) {
			$tmp = $array[$i];
			if ($tmp<$array[$i-1]) {
				$j = $i;
				while (0<$j && $tmp<$array[$j-1]) {
					$array[$j] = $array[$j-1];
					$j--;
				}
				$array[$j] = $tmp;
			}
		}
		return $array;
	}

	// 二分挿入ソート
	public static function binaryInsertionSort(array $array)
	{
		$count = count($array);
		for ($i=1; $i<$count; $i++) {
			$tmp = $array[$i];
			$k = self::binarySearchPos($array, $tmp, 0, $i);
			for ($j=$i; $k<$j; $j--) {
				$array[$j] = $array[$j-1];
			}
			$array[$j] = $tmp;
		}
		return $array;
	}

	// シェルソート
	public static function shellSort(array $array)
	{
		static $incs = array(1391376, 463792, 198768, 86961, 33936, 13776, 4592, 1968, 861, 336, 112, 48, 21, 7, 3, 1);
		$n = count($array);
		for ($k=0; $k<16; $k++) {
			$h = $incs[$k];
			for ($i=$h; $i<$n; $i++) {
				$v = $array[$i];
				$j = $i;
				while ($h<=$j && $v<$array[$j-$h]) {
					$array[$j] = $array[$j-$h];
					$j = $j-$h;
				}
				$array[$j] = $v;
			}
		}
		return $array;
	}

	// ツリーソート
	public static function treeSort(array $array)
	{
		require_once 'BinaryTree.php';
		$bt = new BinaryTree();
		for ($i=0; $i<count($array); $i++) {
			$bt->add($array[$i]);
		}
		return $bt->traverse();
	}

	// ライブラリソート
	public static function librarySort(array $array)
	{
		$size = 4;
		$libraryElements = array();
		$gapCounter = array();

		if (count($array)<=1) {
			return $array;
		}

		// min_element
		$libraryElements[0] = INF;
		for ($i=0; $i<count($array); $i++) {
			if ($array[$i]<$libraryElements[0]) {
				$libraryElements[0] = $array[$i];
			}
		}
		$gapCounter[0] = false;

		// max_element
		$libraryElements[$size-1] = -INF;
		for ($i=0; $i<count($array); $i++) {
			if ($libraryElements[$size-1]<$array[$i]) {
				$libraryElements[$size-1] = $array[$i];
			}
		}
		$gapCounter[$size-1] = false;

		for ($insertPos=0; $insertPos<count($array); $insertPos++) {
			if (($insertPos & ($insertPos+1)) == 0) {
				$size = (($size - 1) * 2 + 1);

				// resize
				for ($i=0; $i<$size; $i++) {
					if (!isset($libraryElements[$i])) {
						$libraryElements[$i] = 0;
						$gapCounter[$i] = true;
					}
				}

				for ($i=$size-1; 0<=$i; $i--) {
					if ($i%2==0) {
						$libraryElements[$i] = $libraryElements[$i>>1];
						$gapCounter[$i] = $gapCounter[$i>>1];
					} else {
						$gapCounter[$i] = true;
					}
				}
			}

			$left = 0;
			$right = $size-1;
			$leftScanPos = 0;
			$rightScanPos = 0;
			while ($left<=$right) {
				$middle = ($left + $right) >> 1;

				if ($gapCounter[$middle]) {
					$leftScanPos = $middle;
					$rightScanPos = $middle;

					while (true) {
						$leftScanPos--;
						$rightScanPos++;
						if ($left<=$leftScanPos && $gapCounter[$leftScanPos]==false) {
							$middle = $leftScanPos;
							break;
						}
						if ($rightScanPos<=$right && $gapCounter[$rightScanPos]==false) {
							$middle = $rightScanPos;
							break;
						}
						if ($leftScanPos<=$left && $right<=$rightScanPos) {
							break 2;
						}
					}
				}

				if ($libraryElements[$middle]<=$array[$insertPos]) {
					$left = ++$middle;
				} else {
					$right = --$middle;
				}
				$middle = $right;
			}

			if ($gapCounter[$middle]!=true) {
				$leftScanPos = $middle;
				$rightScanPos = $middle;

				while (true) {
					$leftScanPos--;
					$rightScanPos++;
					if (0<=$leftScanPos && $gapCounter[$leftScanPos]) {
						for ($i=$leftScanPos; $i<$middle; $i++) {
							$libraryElements[$i] = $libraryElements[$i+1];
						}
						$gapCounter[$leftScanPos] = false;
						break;
					}
					if ($rightScanPos<$size && $gapCounter[$rightScanPos]) {
						$middle++;
						for ($i=$rightScanPos; $middle<$i; $i--) {
							$libraryElements[$i] = $libraryElements[$i-1];
						}
						$gapCounter[$rightScanPos] = false;
						break;
					}
				}
			}

			$libraryElements[$middle] = $array[$insertPos];
			$gapCounter[$middle] = false;
		}

		$isFirstElement = true;
		$insertPos = 0;
		for ($i=0; $i<$size && $insertPos<count($array); $i++) {
			if ($gapCounter[$i]==false) {
				if ($isFirstElement) {
					$isFirstElement = false;
				} else {
					$array[$insertPos] = $libraryElements[$i];
					$insertPos++;
				}
			}
		}

		return $array;
	}

	// ペイシェンスソート
	public static function patienceSort(array $array)
	{
		$piles = array();

		for ($insertPos=0; $insertPos<count($array); $insertPos++) {
			$middle = 0;
			$left = 0;
			$right = count($piles) - 1;

			while ($left<=$right) {
				$middle = (int)(($left+$right) / 2);
				if ($piles[$middle][count($piles[$middle])-1] < $array[$insertPos]) {
					$left = $middle + 1;
				} else {
					$right = $middle - 1;
				}
			}
			if (count($piles)<=$left) {
				// resize
				$piles[] = array();
			}
			$piles[$left][] = $array[$insertPos];
		}

		for ($insertPos=0; $insertPos<count($array); $insertPos++) {
			$array[$insertPos] = $piles[0][count($piles[0])-1];
			unset($piles[0][count($piles[0])-1]);

			if (count($piles[0])==0) {
				$piles[0] = $piles[count($piles)-1];
				unset($piles[count($piles)-1]);
			}

			$root = 0;
			$minChild = 0;
			while ($root<count($piles)) {
				$child1 = $root * 2 + 1;
				$child2 = $root * 2 + 2;

				if ($child1<count($piles) && $piles[$child1][count($piles[$child1])-1]<$piles[$minChild][count($piles[$minChild])-1]) {
					$minChild = $child1;
				}
				if ($child2<count($piles) && $piles[$child2][count($piles[$child2])-1]<$piles[$minChild][count($piles[$minChild])-1]) {
					$minChild = $child2;
				}
				if ($minChild!=$root) {
					list($piles[$root], $piles[$minChild]) = array($piles[$minChild], $piles[$root]);
					$root = $minChild;
				} else {
					break;
				}
			}
		}
		return $array;
	}


	/* マージソート */

	// マージソート
	public static function mergeSort(array $array)
	{
		if (count($array)<=1) {
			return $array;
		}
		if (count($array)==2) {
			return array(min($array), max($array));
		}
		$array1 = array();
		$array2 = array();
		foreach ($array as $i=>$item) {
			if ($i%2==0) {
				$array1[] = $item;
			} else {
				$array2[] = $item;
			}
		}
		$array1 = self::mergeSort($array1);
		$array2 = self::mergeSort($array2);
		$i1 = 0;
		$i2 = 0;
		$result = array();
		while ($i1<count($array1) || $i2<count($array2)) {
			if ($i1<count($array1) && $i2<count($array2)) {
				if ($array1[$i1]<$array2[$i2]) {
					$result[$i1+$i2] = $array1[$i1];
					$i1++;
				} else {
					$result[$i1+$i2] = $array2[$i2];
					$i2++;
				}
			} else if ($i1<count($array1)) {
				$result[$i1+$i2] = $array1[$i1];
				$i1++;
			} else if ($i2<count($array2)){
				$result[$i1+$i2] = $array2[$i2];
				$i2++;
			}
		}
		return $result;
	}

	// 多層マージソート
	public static function polyphaseMergeSort(array $array)
	{
		// todo
	}

	// ストランドソート
	public static function strandSort(array $array)
	{
		$result = array();

		while (count($array)) {
			$sublist = array();
			$sublist[] = array_shift($array);
			$last = count($sublist) - 1;
			foreach ($array as $i=>$value) {
				if ($sublist[$last]<$value) {
					$sublist[] = $value;
					unset($array[$i]);
					$last++;
				}
			}
			if (0<count($result)) {
				foreach ($sublist as $value) {
					$spliced = false;
					foreach ($result as $i=>$rvalue) {
						if ($value<$rvalue) {
							array_splice($result, $i, 0, $value);
							$spliced = true;
							break;
						}
					}
					if (!$spliced) {
						$result[] = $value;
					}
				}
			} else {
				$result = $sublist;
			}
		}
		return $result;
	}

	// ティムソート
	public static function timSort(array $array)
	{
		require_once 'TimSort.php';
		TimSort::sort($array);
		return $array;
	}


	/* 非比較ソート */

	// 基数ソート
	public static function radixSort(array $array)
	{
		$r = 0;
		for ($i=0; $i<count($array); $i++) {
			if ($r<$array[$i]) {
				$r = $array[$i];
			}
		}
		$rad = array();
		$tmp = array();
		$m = 1;
		$n = count($array);
		while ($m<=$r) {
			for ($i=0; $i<$n; $i++) {
				$rad[$i] = ($array[$i] / $m) % 10;
			}
			$k = 0;
			for ($i=0; $i<=9; $i++) {
				for ($j=0; $j<$n; $j++) {
					if ($rad[$j]==$i) {
						$tmp[$k++] = $array[$j];
					}
				}
			}
			$array = $tmp;
			$m *= 10;
		}
		return $array;
	}

	// バケットソート
	public static function bucketSort(array $array)
	{
		$n = count($array);
		$m = 0;
		for ($i=0; $i<$n; $i++) {
			if ($m<$array[$i]) {
				$m = $array[$i];
			}
		}
		$m++;
		$count = array_fill(0, $m, 0);
		$offset = array_fill(0, $m, 0);
		$result = array();
		for ($i=0; $i<$n; $i++) {
			$count[$array[$i]]++;
		}
		$offset[0] = 0;
		for ($i=1; $i<$m; $i++) {
			$offset[$i] = $offset[$i-1] + $count[$i-1];
		}
		for ($i=0; $i<$n; $i++) {
			$target = $array[$i];
			$result[$offset[$target]] = $target;
			$offset[$target]++;
		}
		return $result;
	}

	// カウンティングソート
	public static function countingSort(array $array)
	{
		$n = count($array);
		$min = $array[0];
		$max = $array[0];
		for ($i=1; $i<$n; $i++) {
			if ($array[$i]<$min) {
				$min = $array[$i];
			} else if ($max<$array[$i]) {
				$max = $array[$i];
			}
		}
		$range = $max - $min + 1;
		$count = array();
		for ($i=0; $i<$range; $i++) {
			$count[$i] = 0;
		}
		for ($i=0; $i<$n; $i++) {
			$count[$array[$i]-$min]++;
		}
		$z = 0;
		for ($i=$min; $i<=$max; $i++) {
			for ($j=0; $j<$count[$i-$min]; $j++) {
				$array[$z++] = $i;
			}
		}
		return $array;
	}

	// 鳩の巣ソート
	public static function pigeonholeSort(array $array)
	{
		if (count($array)<=1) {
			return $arrray;
		}

		$min = $array[0];
		$max = $array[0];
		foreach ($array as $value) {
			if ($value<$min) {
				$min = $value;
			}
			if ($max<$value) {
				$max = $value;
			}
		}

		$tmp = array();
		foreach ($array as $value) {
			if (!isset($tmp[$value-$min])) {
				$tmp[$value-$min] = 0;
			}
			$tmp[$value-$min]++;
		}

		$result = array();
		for ($i=0; $i<=$max-$min; $i++) {
			if (isset($tmp[$i])) {
				while (0 < $tmp[$i]--) {
					$result[] = $i+$min;
				}
			}
		}

		return $result;
	}

	// バーストソート
	public static function burstSort(array $array)
	{
		// todo
	}

	// ビーズソート
	public static function beadSort(array $array)
	{
		// todo
	}


	/* その他 */

	// トポロジカルソート
	public static function topologicalSort(array $array)
	{
		// todo
	}

	// バイトニックソート
	public static function bitonicSort(array $array)
	{
		require_once 'BitonicSort.php';
		BitonicSort::sort($array);
		return $array;
	}

	// バッチャー奇偶マージソート
	public static function batcherOddEvenMergeSort(array $array)
	{
		require_once 'BatcherOddEvenMergeSort.php';
		BatcherOddEvenMergeSort::sort($array);
		return $array;
	}

	// パンケーキソート
	public static function pancakeSort(array $array)
	{
		for ($i=count($array)-1; 0<$i; $i--) {
			$max_index = 0;
			$max = $array[0];
			for ($j=1; $j<=$i; $j++) {
				if ($max < $array[$j]) {
					$max_index = $j;
					$max = $array[$j];
				}
			}

			if ($max_index==$i) {
				continue;
			}

			$new_slice = array();
			if (0<$max_index) {
				$new_slice = array_reverse(array_slice($array, 0, $max_index+1));
				for ($j=0; $j<=$max_index; $j++) {
					$array[$j] = $new_slice[$j];
				}
			}

			$new_slice = array_reverse(array_slice($array, 0, $i+1));
			for ($j=0; $j<=$i; $j++) {
				$array[$j] = $new_slice[$j];
			}
		}
		return $array;
	}


	/* 効果なし ユーモラスソート */

	// ボゴソート
	public static function bogoSort(array $array, $loop=100)
	{
		shuffle($array);
		$loop--;
		if (!self::isSorted($array) && 0<$loop) {
			$array = self::bogoSort($array, $loop);
		}
		return $array;
	}

	// ストゥージソート
	public static function stoogeSort(array $array, $i=0, $j=null)
	{
		if (is_null($j)) {
			$j = count($array) - 1;
		}
		if ($array[$j]<$array[$i]) {
			list($array[$i], $array[$j]) = array($array[$j], $array[$i]);
		}
		if (1<$j-$i) {
			$t = (int)(($j - $i + 1) / 3);
			$array = self::stoogeSort($array, $i, $j-$t);
			$array = self::stoogeSort($array, $i+$t, $j);
			$array = self::stoogeSort($array, $i, $j-$t);
		}
		return $array;
	}


	/* 二分木 */

	// 二分探索 値のindexを返す
	public static function binarySearch(array $array, $value, $left=0, $right=null)
	{
		$pos = self::binarySearchPos($array, $value, $left, $right);
		if (0<$pos && $array[$pos-1]==$value) {
			return $pos-1;
		}
		return null;
	}

	// 二分木探索 値を追加するべき位置を返す
	public static function binarySearchPos(array $array, $value, $left=0, $right=null)
	{
		if (is_null($right)) {
			$right = count($array);
		}
		if ($right<$left) {
			list($left, $right) = array($right, $left);
		}

		while ($left<$right) {
			$middle = (int)(($left + $right) / 2);
			if ($array[$middle]<=$value) {
				$left = $middle + 1;
			} else {
				$right = $middle;
			}
		}
		return $right;
	}


	/* util */

	public static function isSorted(array $array)
	{
		$tmp = -INF;
		for ($i=0; $i<count($array); $i++) {
			if ($array[$i]<$tmp) {
				return false;
			}
			$tmp = $array[$i];
		}
		return true;
	}
}

SmoothSort.php

<?php

class SmoothSort
{
	private static $leonardoMemo = array(1, 1);

	public static function leonardo($n)
	{
		if (isset(self::$leonardoMemo[$n]) && self::$leonardoMemo[$n] != 0) {
			return self::$leonardoMemo[$n];
		}
		return self::$leonardoMemo[$n] = self::leonardo($n - 1) + self::leonardo($n - 2) + 1;
	}

	private static function sift(array &$v, $head, $exp)
	{
		$t = $v[$head];
		while (1<$exp) {
			$r = $head - 1;
			$l = $head - 1 - self::leonardo($exp - 2);
			if ($v[$l]<=$t && $v[$r]<=$t) {
				break;
			}
			if ($v[$r]<=$v[$l]) {
				$v[$head] = $v[$l];
				$head = $l;
				$exp -= 1;
			} else {
				$v[$head] = $v[$r];
				$head = $r;
				$exp -= 2;
			}
		}
		$v[$head] = $t;
	}

	private static function arrange(array &$v, $head, $frac, $exp)
	{
		$t = $v[$head];
		while (1<$frac) {
			$next = $head - self::leonardo($exp);
			if ($v[$next]<=$t) {
				break;
			}
			if (1<$exp) {
				$r = $head - 1;
				$l = $head - 1 - self::leonardo($exp - 2);
				if ($v[$next]<=$v[$l] || $v[$next]<=$v[$r]) {
					break;
				}
			}
			$v[$head] = $v[$next];
			$head = $next;
			$trail = self::numberOfTrailingZeros($frac - 1);
			$frac >>= $trail;
			$exp += $trail;
		}
		$v[$head] = $t;
		self::sift($v, $head, $exp);
	}

	public static function sort(array &$v)
	{
		if (count($v)==0) {
			return;
		}
		$head = 0;
		$frac = 0;
		$exp = 0;
		while ($head<count($v)) {
			if (($frac & 3)==3) {
				$frac >>= 2;
				$exp += 2;
			} else if (1<$exp) {
				$frac <<= $exp - 1;
				$exp = 1;
			} else {
				$frac <<= $exp;
				$exp ^= 1;
			}
			$frac++;
			if (0<$exp && count($v)-$head-1<self::leonardo($exp-1)+1) {
				self::arrange($v, $head, $frac, $exp);
			}
			self::sift($v, $head, $exp);
			$head++;
		}
		self::arrange($v, $head - 1, $frac, $exp);
		while (0<$head) {
			$head--;
			if (1<$exp) {
				$frac <<= 2;
				$frac--;
				$exp -= 2;
				self::arrange($v, $head - self::leonardo($exp) - 1, $frac >> 1, $exp+1);
				self::arrange($v, $head - 1, $frac, $exp);
			} else {
				$trail = self::numberOfTrailingZeros($frac - 1);
				$frac >>= $trail;
				$exp += $trail;
			}
		}
	}


	public static function numberOfTrailingZeros($n)
	{
		$i = 0;
		while ($i<=32) {
			if ($n & 1<<$i) {
				return $i;
			}
			$i++;
		}
		return 32;
	}
}

TournamentSort.php

<?php

class TournamentNode
{
	public $data;
	public $index;
	public $active;

	public function __construct()
	{
		$this->data = null;
		$this->index = 0;
		$this->active = false;
	}
}


class TournamentSort
{
	private $a;
	private $tree;

	private function __construct(array &$array)
	{
		$this->a =& $array;
		$this->tree = array();
	}

	public static function sort(array &$array)
	{
		$ts = new TournamentSort($array);
		$ts->tournamentSort();
	}

	private function tournamentSort()
	{
		$a =& $this->a;
		$tree =& $this->tree;

		$n = count($a);

		$bottomRowSize = self::justBitSize($n);
		$treeSize = 2 * $bottomRowSize - 1;
		$loadindex = $bottomRowSize - 1;

		for ($i=0; $i<$treeSize; $i++) {
			$tree[] = new TournamentNode();
		}

		$j = 0;
		for ($i=$loadindex; $i<$treeSize; $i++) {
			$tree[$i]->index = $i;
			if ($j<$n) {
				$tree[$i]->active = true;
				$tree[$i]->data = $a[$j];
				$j++;
			} else {
				$tree[$i]->active = false;
			}
		}

		$i = $loadindex;
		while ($i) {
			$j = $i;
			while ($j < 2*$i) {
				if (!$tree[$j+1]->active || $tree[$j]->data < $tree[$j+1]->data) {
					$tree[($j-1)>>1] = $tree[$j];
				} else {
					$tree[($j-1)>>1] = $tree[$j+1];
				}
				$j += 2;
			}
			$i = ($i-1) >> 1;
		}

		for ($i=0; $i<$n-1; $i++) {
			$a[$i] = $tree[0]->data;
			$tree[$tree[0]->index]->active = false;
			$this->updateTree();
		}
		$a[$n-1] = $tree[0]->data;
	}

	private function updateTree()
	{
		$tree =& $this->tree;
		$i = $tree[0]->index;

		if ($i%2==0) {
			$tree[($i-1)>>1] = $tree[$i-1];
		} else {
			$tree[($i-1)>>1] = $tree[$i+1];
		}

		$i = ($i-1) >> 1;
		while ($i) {
			if ($i%2==0) {
				$j = $i - 1;
			} else {
				$j = $i + 1;
			}
			if (!$tree[$i]->active || !$tree[$j]->active) {
				if ($tree[$i]->active) {
					$tree[($i-1)>>1] = $tree[$i];
				} else {
					$tree[($i-1)>>1] = $tree[$j];
				}
			} else {
				if ($tree[$i]->data < $tree[$j]->data) {
					$tree[($i-1)>>1] = $tree[$i];
				} else {
					$tree[($i-1)>>1] = $tree[$j];
				}
			}
			$i = ($i-1) >> 1;
		}
	}

	private static function justBitSize($n)
	{
		$result = 1;
		while (true) {
			if ($n<=$result) {
				return $result;
			}
			$result <<= 1;
		}
	}
}

BinaryTree.php

<?php

class BinaryNode
{
	public $data;
	public $left;
	public $right;
	public $dup;

	public function __construct($data)
	{
		$this->data = $data;
		$this->left = null;
		$this->right = null;
		$this->dup = 0;
	}
}


class BinaryTree
{
	private $_root;

	// コンストラクタ
	public function __construct()
	{
		$this->_root = null;
	}

	// 要素を追加
	public function add($data)
	{
		$node = new BinaryNode($data);

		$p =& $this->_root;
		while ($p) {
			// 同じデータが登録済み
			if ($p->data==$data) {
				$p->dup++;
				return true;
			// 左へ進む
			} else if ($data<$p->data) {
				$p =& $p->left;
			// 右へ進む
			} else {
				$p =& $p->right;
			}
		}

		$p = $node;
		return true;
	}

	// 要素を削除
	public function delete($data)
	{
		$p =& $this->_root;
		while ($p) {
			// 発見
			if ($p->data==$data) {
				//  重複数を減らす
				if (0<$p->dup) {
					$p->dup--;
				// ノードを削除
				} else {
					// 左右両方あり
					if ($p->left && $p->right) {
						$p2 =& $p->right;
						while ($p2->left) {
							$p2 =& $p2->left;
						}
						$p2->left = $p->left;
						$p = $p->right;
					// 左あり
					} else if ($p->left) {
						$p = $p->left;
					// 右あり
					} else if ($p->right) {
						$p = $p->right;
					} else {
						$p = null;
					}
				}
				return true;
			}

			// 左へ進む
			if ($data<$p->data) {
				$p =& $p->left;
			// 右へ進む
			} else {
				$p =& $p->right;
			}
		}
		return false;
	}

	// 要素を検索
	public function search($data)
	{
		$p =& $this->_root;
		while ($p) {
			// 発見
			if ($p->data==$data) {
				return $p;
			// 左へ進む
			} else if ($data<$p->data) {
				$p =& $p->left;
			// 右へ進む
			} else {
				$p =& $p->right;
			}
		}
		return null;
	}

	// 要素を配列で取得
	public function traverse(BinaryNode $p=null)
	{
		if (!$p) {
			$p = $this->_root;
		}
		$result = array();
		if ($p) {
			if ($p->left) {
				$result = array_merge($result, $this->traverse($p->left));
			}
			for ($i=0; $i<=$p->dup; $i++) {
				$result[] = $p->data;
			}
			if ($p->right) {
				$result = array_merge($result, $this->traverse($p->right));
			}
		}
		return $result;
	}
}

TimSort.php

<?php

class TimSort
{
	const MIN_MERGE = 32;
	private $a;
	const MIN_GALLOP = 7;
	private $minGallop = 7;
	const INITIAL_TMP_STORAGE_LENGTH = 256;
	private $tmp;
	private $stackSize = 0;
	private $runBase;
	private $runLen;

	private function __construct(array &$a)
	{
		$this->a =& $a;

		$len = count($a);
		$tmpLen = $len < 2 * self::INITIAL_TMP_STORAGE_LENGTH ? $len >> 1 : INITIAL_TMP_STORAGE_LENGTH;
		$this->tmp = array_fill(0, $tmpLen, null);

		$this->runBase = array();
		$this->runLen = array();
	}

	public static function sort(array &$a, $lo=0, $hi=null)
	{
		if (is_null($hi)) {
			$hi = count($a);
		}

		self::rangeCheck(count($a), $lo, $hi);
		$nRemaining  = $hi - $lo;
		if ($nRemaining < 2) {
			return;		// Arrays of size 0 and 1 are always sorted
		}

		// If array is small, do a "mini-TimSort" with no merges
		if ($nRemaining < self::MIN_MERGE) {
			$initRunLen = self::countRunAndMakeAscending($a, $lo, $hi);
			self::binarySort($a, $lo, $hi, $lo + $initRunLen);
			return;
		}

		$ts = new TimSort($a);
		$minRun = self::minRunLength($nRemaining);
		do {
			// Identify next run
			$runLen = self::countRunAndMakeAscending($a, $lo, $hi);

			// If run is short, extend to min(minRun, nRemaining)
			if ($runLen < $minRun) {
				$force = $nRemaining <= $minRun ? $nRemaining : $minRun;
				self::binarySort($a, $lo, $lo + $force, $lo + $runLen);
				$runLen = $force;
			}

			// Push run onto pending-run stack, and maybe merge
			$ts->pushRun($lo, $runLen);
			$ts->mergeCollapse();

			// Advance to find next run
			$lo += $runLen;
			$nRemaining -= $runLen;
		} while ($nRemaining != 0);

		// Merge all remaining runs to complete sort
		if (!($hi==$lo)) {
			throw new Exception("assert lo == hi;");
		}
		$ts->mergeForceCollapse();
		if (!($ts->stackSize==1)) {
			throw new Exception("assert ts.stackSize == 1;");
		}
	}

	private static function binarySort(array &$a, $lo, $hi, $start)
	{
		if (!($lo <= $start && $start <= $hi)) {
			throw new Exception("assert lo <= start && start <= hi;");
		}
		if ($start == $lo) {
			$start++;
		}
		for ( ; $start < $hi; $start++) {
			$pivot = $a[$start];

			// Set left (and right) to the index where a[start] (pivot) belongs
			$left = $lo;
			$right = $start;
			if (!($left <= $right)) {
				throw new Exception("assert left <= right;");
			}

			while ($left < $right) {
				$mid = ($left + $right) >> 1;
				if ($pivot<$a[$mid]) {
					$right = $mid;
				} else {
					$left = $mid + 1;
				}
			}
			if (!($left == $right)) {
				throw new Exception("assert left == right;");
			}

			$n = $start - $left;	// The number of elements to move
			// Switch is just an optimization for arraycopy in default case
			switch($n) {
			case 2:
				$a[$left+2] = $a[$left+1];
			case 1:
				$a[$left+1] = $a[$left];
				break;
			default:
				self::arraycopy($a, $left, $a, $left + 1, $n);
			}
			$a[$left] = $pivot;
		}
	}

	private static function countRunAndMakeAscending(array &$a, $lo, $hi)
	{
		if (!($lo < $hi)) {
			throw new Exception("assert lo < hi;");
		}

		$runHi = $lo + 1;
		if ($runHi == $hi) {
			return 1;
		}

		// Find end of run, and reverse range if descending
		if ($a[$runHi++] < $a[$lo]) {
			while ($runHi < $hi && $a[$runHi] < $a[$runHi - 1]) {
				$runHi++;
			}
			self::reverseRange($a, $lo, $runHi);
		} else {
			while ($runHi < $hi && $a[$runHi] >= $a[$runHi - 1]) {
				$runHi++;
			}
		}
		return $runHi - $lo;
	}

	private static function reverseRange(array &$a, $lo, $hi)
	{
		$hi--;
		while ($lo < $hi) {
			$t = $a[$lo];
			$a[$lo++] = $a[$hi];
			$a[$hi--] = $t;
		}
	}

	private static function minRunLength($n)
	{
		if (!($n >= 0)) {
			throw new Exception("assert n >= 0;");
		}
		$r = 0;		// Becomes 1 if any 1 bits are shifted off
		while ($n >= self::MIN_MERGE) {
			$r |= ($n & 1);
			$n >>= 1;
		}
		return $n +$r;
	}

	private function pushRun($runBase, $runLen)
	{
		$this->runBase[$this->stackSize] = $runBase;
		$this->runLen[$this->stackSize] = $runLen;
		$this->stackSize++;
	}

	private function mergeCollapse()
	{
		while ($this->stackSize > 1) {
			$n = $this->stackSize - 2;
			if ($n > 0 && $this->runLen[$n-1] <= $this->runLen[$n] + $this->runLen[$n+1]) {
				if ($this->runLen[$n - 1] < $this->runLen[$n + 1]) {
					$n--;
				}
				$this->mergeAt($n);
			} else if ($this->runLen[$n] <= $this->runLen[$n + 1]) {
				$this->mergeAt($n);
			} else {
				break;		// Invariant is established
			}
		}
	}

	private function mergeForceCollapse()
	{
		while ($this->stackSize > 1) {
			$n = $this->stackSize - 2;
			if ($n > 0 && $this->runLen[$n - 1] < $this->runLen[$n + 1]) {
				$n--;
			}
			$this->mergeAt($n);
		}
	}

	private function mergeAt($i)
	{
		if (!($this->stackSize >= 2)) {
			throw new Exception("assert stackSize >= 2;");
		}
		if (!($i >= 0)) {
			throw new Exception("assert i >= 0;");
		}
		if (!($i == $this->stackSize - 2 || $i == $this->stackSize - 3)) {
			throw new Exception("assert i == stackSize - 2 || i == stackSize - 3;");
		}

		$base1 = $this->runBase[$i];
		$len1 = $this->runLen[$i];
		$base2 = $this->runBase[$i + 1];
		$len2 = $this->runLen[$i + 1];

		if (!($len1 > 0 && $len2 > 0)) {
			throw new Exception("assert len1 > 0 && len2 > 0;");
		}
		if (!($base1 + $len1 == $base2)) {
			throw new Exception("assert base1 + len1 == base2;");
		}

		$this->runLen[$i] = $len1 + $len2;
		if ($i == $this->stackSize - 3) {
			$this->runBase[$i + 1] = $this->runBase[$i + 2];
			$this->runLen[$i + 1] = $this->runLen[$i + 2];
		}
		$this->stackSize--;

		$k = self::gallopRight($this->a[$base2], $this->a, $base1, $len1, 0);
		if (!($k >= 0)) {
			throw new Exception("assert k >= 0;");
		}
		$base1 += $k;
		$len1 -= $k;
		if ($len1 == 0) {
			return;
		}

		$len2 = self::gallopLeft($this->a[$base1 + $len1 - 1], $this->a, $base2, $len2, $len2 - 1);
		if (!($len2 >= 0)) {
			throw new Exception("assert len2 >= 0;");
		}
		if ($len2 == 0) {
			return;
		}

		// Merge remaining runs, using tmp array with min(len1, len2) elements
		if ($len1 <= $len2) {
			$this->mergeLo($base1, $len1, $base2, $len2);
		} else {
			$this->mergeHi($base1, $len1, $base2, $len2);
		}
	}

	private static function gallopLeft($key, array &$a, $base, $len, $hint)
	{
		if (!($len > 0 && $hint >= 0 && $hint < $len)) {
			throw new Exception("assert len > 0 && hint >= 0 && hint < len;");
		}

		$lastOfs = 0;
		$ofs = 1;
		if ($key > $a[$base + $hint]) {
			$maxOfs = $len - $hint;
			while ($ofs < $maxOfs && $key > $a[$base + $hint + $ofs]) {
				$lastOfs = $ofs;
				$ofs = ($ofs << 1) + 1;
				if ($ofs <= 0) {	// int overflow
					$ofs = $maxOfs;
				}
			}
			if ($ofs > $maxOfs) {
				$ofs = $maxOfs;
			}

			// Make offsets relative to base
			$lastOfs += $hint;
			$ofs += $hint;
		} else {	// key <= a[base + hint]
			// Gallop left until a[base+hint-ofs] < key <= a[base+hint-lastOfs]
			$maxOfs = $hint + 1;
			while ($ofs < $maxOfs && $key <= $a[$base + $hint - $ofs]) {
				$lastOfs = $ofs;
				$ofs = ($ofs << 1) + 1;
				if ($ofs <= 0) {	// int overflow
					$ofs = $maxOfs;
				}
			}
			if ($ofs > $maxOfs) {
				$ofs = $maxOfs;
			}

			// Make offsets relative to base
			$tmp = $lastOfs;
			$lastOfs = $hint - $ofs;
			$ofs = $hint - $tmp;
		}
		if (!(-1 <= $lastOfs && $lastOfs < $ofs && $ofs <= $len)) {
			throw new Exception("assert -1 <= lastOfs && lastOfs < ofs && ofs <= len;");
		}

		$lastOfs++;
		while ($lastOfs < $ofs) {
			$m = $lastOfs + (($ofs - $lastOfs) >> 1);
			if ($key > $a[$base + $m]) {
				$lastOfs = $m + 1;	// a[base + m] < key
			} else {
				$ofs = $m;			// key <= a[base + m]
			}
		}
		if (!($lastOfs == $ofs)) {
			throw new Exception("assert lastOfs == ofs;");
		}
		return $ofs;
	}

	private static function gallopRight($key, array &$a, $base, $len, $hint)
	{
		if (!($len > 0 && $hint >= 0 && $hint < $len)) {
			throw new Exception("assert len > 0 && hint >= 0 && hint < len;");
		}

		$ofs = 1;
		$lastOfs = 0;
		if ($key < $a[$base + $hint]) {
			// Gallop left until a[b+hint - ofs] <= key < a[b+hint - lastOfs]
			$maxOfs = $hint + 1;
			while ($ofs < $maxOfs && $key < $a[$base + $hint - $ofs]) {
				$lastOfs = $ofs;
				$ofs = ($ofs << 1) + 1;
				if ($ofs <= 0) {	// int overflow
					$ofs = $maxOfs;
				}
			}
			if ($ofs > $maxOfs) {
				$ofs = $maxOfs;
			}

			// Make offsets relative to b
			$tmp = $lastOfs;
			$lastOfs = $hint - $ofs;
			$ofs = $hint - $tmp;
		} else {	// a[b + hint] <= key
			// Gallop right until a[b+hint + lastOfs] <= key < a[b+hint + ofs]
			$maxOfs = $len - $hint;
			while ($ofs < $maxOfs && $key >= $a[$base + $hint + $ofs]) {
				$lastOfs = $ofs;
				$ofs = ($ofs << 1) + 1;
				if ($ofs <= 0) {	// int overflow
					$ofs = $maxOfs;
				}
			}
			if ($ofs > $maxOfs) {
				$ofs = $maxOfs;
			}

			// Make offsets relative to b
			$lastOfs += $hint;
			$ofs += $hint;
		}
		if (!(-1 <= $lastOfs && $lastOfs < $ofs && $ofs <= $len)) {
			throw new Exception("assert -1 <= lastOfs && lastOfs < ofs && ofs <= len;");
		}

		$lastOfs++;
		while ($lastOfs < $ofs) {
			$m = $lastOfs + (($ofs - $lastOfs) >> 1);
			if ($key < $a[$base + $m]) {
				$ofs = $m;			// key < a[b + m]
			} else {
				$lastOfs = $m + 1;	// a[b + m] <= key
			}
		}
		if (!($lastOfs == $ofs)) {
			throw new Exception("assert lastOfs == ofs;");		// so a[b + ofs - 1] <= key < a[b + ofs]
		}
		return $ofs;
	}

	private function mergeLo($base1, $len1, $base2, $len2)
	{
		if (!($len1 > 0 && $len2 > 0 && $base1 + $len1 == $base2)) {
			throw new Exception("assert len1 > 0 && len2 > 0 && base1 + len1 == base2;");
		}

		// Copy first run into temp array
		$a =& $this->a;
		$tmp = $this->ensureCapacity($len1);
		self::arraycopy($a, $base1, $tmp, 0, $len1);

		$cursor1 = 0;
		$cursor2 = $base2;
		$dest = $base1;

		// Move first element of second run and deal with degenerate cases
		$a[$dest++] = $a[$cursor2++];
		if (--$len2 == 0) {
			self::arraycopy($tmp, $cursor1, $a, $dest, $len1);
			return;
		}
		if ($len1 == 1) {
			self::arraycopy($a, $cursor2, $a, $dest, $len2);
			$a[$dest + $len2] = $tmp[$cursor1];	// Last elt of run 1 to end of merge
			return;
		}

		$minGallop = $this->minGallop;
		while (true) {
			$count1 = 0; // Number of times in a row that first run won
			$count2 = 0; // Number of times in a row that second run won

			do {
				if (!($len1 > 1 && $len2 > 0)) {
					throw new Exception("assert len1 > 1 && len2 > 0;");
				}
				if ($a[$cursor2] < $tmp[$cursor1]) {
					$a[$dest++] = $a[$cursor2++];
					$count2++;
					$count1 = 0;
					if (--$len2 == 0) {
						break 2;
					}
				} else {
					$a[$dest++] = $tmp[$cursor1++];
					$count1++;
					$count2 = 0;
					if (--$len1 == 1) {
						break 2;
					}
				}
			} while (($count1 | $count2) < $minGallop);

			do {
				if (!($len1 > 1 && $len2 > 0)) {
					throw new Exception("assert len1 > 1 && len2 > 0;");
				}
				$count1 = self::gallopRight($a[$cursor2], $tmp, $cursor1, $len1, 0);
				if ($count1 != 0) {
					self::arraycopy($tmp, $cursor1, $a, $dest, $count1);
					$dest += $count1;
					$cursor1 += $count1;
					$len1 -= $count1;
					if ($len1 <= 1) {	// len1 == 1 || len1 == 0
						break 2;
					}
				}
				$a[$dest++] = $a[$cursor2++];
				if (--$len2 == 0) {
					break 2;
				}
				$count2 = self::gallopLeft($tmp[$cursor1], $a, $cursor2, $len2, 0);
				if ($count2 != 0) {
					self::arraycopy($a, $cursor2, $a, $dest, $count2);
					$dest += $count2;
					$cursor2 += $count2;
					$len2 -= $count2;
					if ($len2 == 0) {
						break 2;
					}
				}
				$a[$dest++] = $tmp[$cursor1++];
				if (--$len1 == 1) {
					break 2;
				}
				$minGallop--;
			} while ($count1 >= self::MIN_GALLOP | $count2 >= self::MIN_GALLOP);
			if ($minGallop < 0) {
				$minGallop = 0;
			}
			$minGallop += 2;	// Penalize for leaving gallop mode
		}
		$this->minGallop = $minGallop < 1 ? 1 : $minGallop;		// Write back to field

		if ($len1 == 1) {
			if (!($len2 > 0)) {
				throw new Exception("assert len2 > 0;");
			}
			self::arraycopy($a, $cursor2, $a, $dest, $len2);
			$a[$dest + $len2] = $tmp[$cursor1];	// Last elt of run 1 to end of merge
		} else if ($len1 == 0) {
			throw new Exception("IllegalArgumentException: Comparison method violates its general contract!");
		} else {
			if (!($len2 == 0)) {
				throw new Exception("assert len2 == 0;");
			}
			if (!($len1 > 1)) {
				throw new Exception("assert len1 > 1;");
			}
			self::arraycopy($tmp, $cursor1, $a, $dest, $len1);
		}
	}

	private function mergeHi($base1, $len1, $base2, $len2)
	{
		if (!($len1 > 0 && $len2 > 0 && $base1 + $len1 == $base2)) {
			throw new Exception("assert len1 > 0 && len2 > 0 && base1 + len1 == base2;");
		}

		// Copy second run into temp array
		$a =& $this->a;
		$tmp = $this->ensureCapacity($len2);
		self::arraycopy($a, $base2, $tmp, 0, $len2);

		$cursor1 = $base1 + $len1 - 1;
		$cursor2 = $len2 - 1;
		$dest = $base2 + $len2 - 1;

		// Move last element of first run and deal with degenerate cases
		$a[$dest--] = $a[$cursor1--];
		if (--$len1 == 0) {
			self::arraycopy($tmp, 0, $a, $dest - ($len2 - 1), $len2);
			return;
		}
		if ($len2 == 1) {
			$dest -= $len1;
			$cursor1 -= $len1;
			self::arraycopy($a, $cursor1 + 1, $a, $dest + 1, $len1);
			$a[$dest] = $tmp[$cursor2];
			return;
		}

		$minGallop = $this->minGallop;
		while (true) {
			$count1 = 0;	// Number of times in a row that first run won
			$count2 = 0;	// Number of times in a row that second run won

			do {
				if (!($len1 > 0 && $len2 > 1)) {
					throw new Exception("assert len1 > 0 && len2 > 1;");
				}
				if ($tmp[$cursor2] < $a[$cursor1]) {
					$a[$dest--] = $a[$cursor1--];
					$count1++;
					$count2 = 0;
					if (--$len1 == 0) {
						break 2;
					}
				} else {
					$a[$dest--] = $tmp[$cursor2--];
					$count2++;
					$count1 = 0;
					if (--$len2 == 1) {
						break 2;
					}
				}
			} while (($count1 | $count2) < $minGallop);

			do {
				if (!($len1 > 0 && $len2 > 1)) {
					throw new Exception("assert len1 > 0 && len2 > 1;");
				}
				$count1 = $len1 - self::gallopRight($tmp[$cursor2], $a, $base1, $len1, $len1 - 1);
				if ($count1 != 0) {
					$dest -= $count1;
					$cursor1 -= $count1;
					$len1 -= $count1;
					self::arraycopy($a, $cursor1 + 1, $a, $dest + 1, $count1);
					if ($len1 ==0) {
						break 2;
					}
				}
				$a[$dest--] = $tmp[$cursor2--];
				if (--$len2 == 1) {
					break 2;
				}

				$count2 = $len2 - self::gallopLeft($a[$cursor1], $tmp, 0, $len2, $len2 - 1);
				if ($count2 != 0) {
					$dest -= $count2;
					$cursor2 -= $count2;
					$len2 -= $count2;
					self::arraycopy($tmp, $cursor2 + 1, $a, $dest + 1, $count2);
					if ($len2 <= 1) {	// len2 == 1 || len2 == 0
						break 2;
					}
				}
				$a[$dest--] = $a[$cursor1--];
				if (--$len1 == 0) {
					break 2;
				}
				$minGallop--;
			} while ($count1 >= self::MIN_GALLOP | $count2 >= self::MIN_GALLOP);
			if ($minGallop < 0) {
				$minGallop = 0;
			}
			$minGallop += 2;	// Penalize for leaving gallop mode
		}
		$this->minGallop = $minGallop < 1 ? 1 : $minGallop;

		if ($len2 == 1) {
			if (!($len1 > 0)) {
				throw new Exception("assert len1 > 0;");
			}
			$dest -= $len1;
			$cursor1 -= $len1;
			self::arraycopy($a, $cursor1 + 1, $a, $dest + 1, $len1);
			$a[$dest] = $tmp[$cursor2];	// Move first elt of run2 to front of merge
		} else if ($len2 ==0) {
			throw new Exception("IllegalArgumentException: Comparison method violates its general contract!");
		} else {
			if (!($len1 == 0)) {
				throw new Exception("assert len1 == 0;");
			}
			if (!($len2 > 0)) {
				throw new Exception("assert len2 > 0;");
			}
			self::arraycopy($tmp, 0, $a, $dest - ($len2 - 1), $len2);
		}
	}

	private function &ensureCapacity($minCapacity)
	{
		if (count($this->tmp) < $minCapacity) {
			$newSize = $minCapacity;
			$newSize |= $newSize >> 1;
			$newSize |= $newSize >> 2;
			$newSize |= $newSize >> 4;
			$newSize |= $newSize >> 8;
			$newSize |= $newSize >> 16;
			$newSize++;

			if ($newSize < 0) {
				$newSize = $minCapacity;
			} else {
				$newSize = min($newSize, count($this->a) >> 1);
			}
			$this->tmp = array_fill(0, $newSize, null);
		}
		return $this->tmp;
	}

	private static function rangeCheck($arrayLen, $fromIndex, $toIndex)
	{
		if ($fromIndex > $toIndex) {
			throw new Exception("IllegalArgumentException: fromIndex(" . $fromIndex . ") > toIndex(" . $toIndex . ")");
		}
		if ($fromIndex < 0) {
			throw new Exception("ArrayIndexOutOfBoundsException: " . $fromIndex);
		}
		if ($toIndex > $arrayLen) {
			throw new Exception("ArrayIndexOutOfBoundsException: " . $toIndex);
		}
	}


	public static function arraycopy(array $from, $from_i, array &$to, $to_i, $n)
	{
		$tmp_arr = array_slice($from, $from_i, $n);
		foreach ($tmp_arr as $tmp_item) {
			$to[$to_i] = $tmp_item;
			$to_i++;
		}
	}
}

BitonicSort.php

<?php

class BitonicSort
{
	const ASCENDING = true;
	const DESCENDING = false;

	private $a;
	private $size;

	private function __construct(array &$a)
	{
		$this->a =& $a;
		$this->size = count($a);
	}

	public static function sort(array &$a)
	{
		$org_size = count($a);
		$add_size = self::justBitSize(count($a)) - $org_size;
		while (0<$add_size--) {
			$a[] = INF;
		}
		$bs = new BitonicSort($a);
		$bs->bitonicSort(0, count($a), self::ASCENDING);
		array_splice($a, $org_size);
	}

	private static function justBitSize($n)
	{
		$result = 1;
		while (true) {
			if ($n<=$result) {
				return $result;
			}
			$result <<= 1;
		}
	}

	private function bitonicSort($lo, $n, $dir)
	{
		if (1<$n) {
			$m = $n >> 1;
			$this->bitonicSort($lo, $m, self::ASCENDING);
			$this->bitonicSort($lo+$m, $m, self::DESCENDING);
			$this->bitonicMerge($lo, $n, $dir);
		}
	}

	private function bitonicMerge($lo, $n, $dir)
	{
		if (1<$n) {
			$m = $n >> 1;
			for ($i=$lo; $i<$lo+$m; $i++) {
				$this->compare($i, $i+$m, $dir);
			}
			$this->bitonicMerge($lo, $m, $dir);
			$this->bitonicMerge($lo+$m, $m, $dir);
		}
	}

	private function compare($i, $j, $dir)
	{
		if ($dir==($this->a[$j]<$this->a[$i])) {
			$this->exchange($i, $j);
		}
	}

	private function exchange($i, $j)
	{
		list($this->a[$i], $this->a[$j]) = array($this->a[$j], $this->a[$i]);
	}
}

BatcherOddEvenMergeSort.php

<?php

class BatcherOddEvenMergeSort
{
	private $a;

	private function __construct(array &$a)
	{
		$this->a =& $a;
	}

	public static function sort(array &$a)
	{
		$org_size = count($a);
		$add_size = self::justBitSize(count($a)) - $org_size;
		while (0<$add_size--) {
			$a[] = INF;
		}
		$oems = new BatcherOddEvenMergeSort($a);
		$oems->oddEvenMergeSort(0, count($a));
		array_splice($a, $org_size);
	}

	private static function justBitSize($n)
	{
		$result = 1;
		while (true) {
			if ($n<=$result) {
				return $result;
			}
			$result <<= 1;
		}
	}

	private function oddEvenMergeSort($lo, $n)
	{
		if (1<$n) {
			$m = $n >> 1;
			$this->oddEvenMergeSort($lo, $m);
			$this->oddEvenMergeSort($lo+$m, $m);
			$this->oddEvenMerge($lo, $n, 1);
		}
	}

	private function oddEvenMerge($lo, $n, $r)
	{
		$m = $r << 1;
		if ($m<$n) {
			$this->oddEvenMerge($lo, $n, $m);
			$this->oddEvenMerge($lo+$r, $n, $m);
			for ($i=$lo+$r; $i+$r<$lo+$n; $i+=$m) {
				$this->compare($i, $i+$r);
			}
		} else {
			$this->compare($lo, $lo+$r);
		}
	}

	private function compare($i, $j)
	{
		if ($this->a[$j]<$this->a[$i]) {
			$this->exchange($i, $j);
		}
	}

	private function exchange($i, $j)
	{
		list($this->a[$i], $this->a[$j]) = array($this->a[$j], $this->a[$i]);
	}
}