PHP: Алгоритм быстрая сортировка

Сортировка массива с помощью алгоритма «Быстрая сортировка».

В каждой итерации выбираем опорное значение и разделяем массив на значения больше и меньше опорного значения.

Сложность: O(n log n)

// тестовый массив
$data = [ 8, 99, 1, 3, 10, 199, 2, 8, 3, 99, 3 ]; 

Решение с удалением повторяющихся значений:

function qsort( $arr ) 
{ 
	if( sizeof( $arr ) < 2 )	
	{ 
		return $arr; 
	} 
	else 
	{ 
		$baseIndex = 0;
		// в качестве опорного значения можно взять любое из массива
		// $baseIndex = rand( 0, sizeof( $arr ) - 1 );
		$base = $arr[ $baseIndex ];
		$lt = []; 
		$gt = []; 
		$mid = [ $base ]; 
		foreach( $arr as $index => $value ) 
		{ 
			if( $value > $base ) 
			{ 
				array_push( $gt, $value ); 
			} 
			else if( $value < $base ) 
			{ 
				array_push( $lt, $value ); 
			} 			
		}
		return array_merge( qsort( $lt ), $mid, qsort( $gt ) ); 
	} 
} 

echo '<pre>', var_dump( qsort( $data ) ) ,'</pre>';
// > array(7) {
// >   [0]=>
// >   int(1)
// >   [1]=>
// >   int(2)
// >   [2]=>
// >   int(3)
// >   [3]=>
// >   int(8)
// >   [4]=>
// >   int(10)
// >   [5]=>
// >   int(99)
// >   [6]=>
// >   int(199)
// > }}

Решение с сохранением повторяющихся значений:

function qsortWithRepeats( $arr ) 
{ 
	if( sizeof( $arr ) < 2 )	
	{ 
		return $arr; 
	} 
	else 
	{ 
		$baseIndex = 0;
		$base = $arr[ $baseIndex ];
		$lt = []; 
		$gt = []; 
		$mid = [ $base ]; 
		foreach( $arr as $index => $value ) 
		{ 
			if( $value > $base ) 
			{ 
				array_push( $gt, $value ); 
			} 
			else if( $value < $base ) 
			{ 
				array_push( $lt, $value ); 
			} 
			else if( $index != $baseIndex AND $value == $base ) 
			{ 
				array_push( $mid, $value ); 
			} 
		}
		return array_merge( qsortWithRepeats( $lt ), $mid, qsortWithRepeats( $gt ) ); 
	} 
} 

echo '<pre>', var_dump( qsortWithRepeats( $data ) ) ,'</pre>';
// > array(11) {
// >   [0]=>
// >   int(1)
// >   [1]=>
// >   int(2)
// >   [2]=>
// >   int(3)
// >   [3]=>
// >   int(3)
// >   [4]=>
// >   int(3)
// >   [5]=>
// >   int(8)
// >   [6]=>
// >   int(8)
// >   [7]=>
// >   int(10)
// >   [8]=>
// >   int(99)
// >   [9]=>
// >   int(99)
// >   [10]=>
// >   int(199)
// > }