TRI FUSION - MERGESORT

<?php
//////////////////////////////////////////////////////////////////////
// fusion.php
//--------------------------------------------------------------------
//
// Tri par fusion - MergeSort
// Prend un tableau et le sépare en 2. Ensuite prend chaque tableau
// et separe ceux-ci encore en 2. Jusqu'à ce qu'il ne reste qu'un seul
// élément.
// Ensuite, avec chaque petit tableau de 1 on refait le gros tableau
// en comparant à chaque fois chaque élément.
// Pour mieux comprendre, il vous faut un dessin ! Cherchez sur Google
// tri fusion.
// La complexité de cet algorithme est de O(n log n)
//
// Ce script a été réalisé avec 2 autres coéquipiers en C
// mais il a été transféré en PHP par Jean-Sébastien Goupil
//
//--------------------------------------------------------------------
// Revision History
// V1.00	23 aug	2004	Jean-Sebastien Goupil
//--------------------------------------------------------------------
// Copyright (C) Jean-Sebastien Goupil
// http://other.lookstrike.com/
//--------------------------------------------------------------------
//////////////////////////////////////////////////////////////////////
function triFusion ( &$tab ) {
	 if( count( $tab ) <= 1 ) return;
	 else {
		$tab1 = array();
		$tab2 = array();

		// Répartie les information dans 2 tableaux différent
		for( $i = 0; $i < count( $tab ); $i++) {
			if( $i < ( count( $tab ) ) / 2 )
				$tab1[] = $tab[ $i ];
			else
				$tab2[] = $tab[ $i ];
		}

		// Appel la fonction tri récursivement
		triFusion( $tab1 );
		triFusion( $tab2 );

		// Fusionne les petits tableaux en plus grand
		fusionner( $tab1, $tab2, $tab );
	}
}

function fusionner ( $tab1, $tab2, &$tab ) {
	$i = 0;
	$i1 = $i2 = 0;
	// Fusionne les petits tableaux dans le plus grand
	while( $i1 < count( $tab1 ) && $i2 < count( $tab2 ) ) {
		if( $tab1[ $i1 ] < $tab2[ $i2 ] ) // On compare ici
			$tab[ $i ] = $tab1[ $i1++ ];
		else
			$tab[ $i ] = $tab2[ $i2++ ];
		$i++;
	}

	// S'il reste des éléments dans un des 2 tableaux mais pas dans l'autre
	while( $i1 < count( $tab1 ) ) {
		$tab[ $i ] = $tab1[ $i1++ ];
		$i++;
	}
	while( $i2 < count( $tab2 ) ) {
		$tab[ $i ] = $tab2[ $i2++ ];
		$i++;
	}
}

$a = split(' ','Voici un tri par fusion !');
triFusion ( $a );
print_r($a);
?>