// tri rapide avec insertion

proc _quick_insertion_sort( t is array[1..n] of int; a, b are int) 

	if (b - a) > 15 then
		if a < b then
		
			// pivot in the middle of the array
			var m = (b + a + 1) / 2
			var x = t[ m ]
			
			swap( t[ m ], t[ b ] )

			var q = a
			for i in a..b-1 do
				
				if t[ i ] < x then
					swap( t[ i ], t [q++ ])
				end if	
				
			end for
			
			swap( t[ b ], t[ q ] )
					
			if (a < q) _quick_insertion_sort( t, a, q - 1 )
			if (q < b) _quick_insertion_sort( t, q + 1, b )

	else
		
		insertion_sort( t,  a , b );
				
	end if
	
end proc



proc quick_insertion_sort( t is array[1..n] of int ) 

	_quick_insertion_sort( t, 1, n )

end proc