Insertion sorts are good when your data is already partially sorted, or if you have a small collection to sort. That’s about the best I can say for them. Here’s two versions in PHP. The first uses two functions:

function insertion_sort($a)
{
for ($i=1; $i < count($a); $i++) { inserter(&$a,$i,$a[$i]); } }

function inserter($a,$pos,$a_value)
{
$temp = $a[$pos];
$i = $pos;
while($i >= 0 && $a[$i-1] > $a_value)
{
$a[$i] = $a[$i-1];
$i = $i-1;
}
$a[$i] = $temp;
}


The second uses one function:


function insertion_sort($a)
{
for($j=1; $j < count($a); $j++) { $temp = $a[$j]; $i = $j; while(($i >= 0) && ($a[$i-1] > $temp)){
$a[$i] = $a[$i-1];
$i--;
}
$a[$i] = $temp;
}
}


To test them, use the following code:


$haystack = array(1,5,6,3);
insertion_sort(&$haystack);
print_r ($haystack);