incremental_rand_sort.php

<?php

class CardDeck {
	public $deck = Array();

	public function __construct(int $size) {
		for ($i=1; $i <= $size; $i++) { 
			$this->deck[] = Array($i);
		}

		shuffle($this->deck);
	}

	public function combineGroups() {
		for ($i=0; $i < count($this->deck)-1; $i++) { 
			if ($this->deck[$i][count($this->deck[$i])-1] + 1 == $this->deck[$i+1][0]) {
				$this->deck[$i] = array_merge($this->deck[$i], $this->deck[$i+1]);
				unset($this->deck[$i+1]);
				$this->deck = array_values($this->deck); // reindex
				$i--;
			}
		}
	}

	public function __toString() : string {
		$dashes = "";
		$cards = "";

		foreach ($this->deck as $subdeck) {
			$dashes .= str_repeat("-", count($subdeck));
			$cards .= array_reduce($subdeck, function($a, $b) { return $a.$b; });

			$dashes .= " ";
			$cards .= " ";
		}

		return $dashes."\n".$cards."\n";
	}

	public function shuffle() {
		$this->combineGroups();
		shuffle($this->deck);
	}

	public function shuffleUntilOrdered() : int {
		$numShuffles = 0;

		$this->combineGroups();
		while (count($this->deck) != 1) {
			$numShuffles++;
			$this->shuffle();
		}

		return $numShuffles;
	}
}

$total = 0;
for ($i=0; $i < 100; $i++) { 
	echo "#";
	for ($j=0; $j < 10000; $j++) { 
		$deck = new CardDeck(52);
		$total += $deck->shuffleUntilOrdered();
	}
}

var_export($total);